C++ O(N), array instead of unordered_map.


  • 5
    V

    This is the same as "325. Maximum Size Subarray Sum Equals k" (https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/), where zeros are -1, ones are ones, and k is zero. Since in this problem the range of possible sums is [-size...size], we can use an array instead of unordered_map. We can consider size as the zero point, so the array indexes will be [0... 2 * size].

    int findMaxLength(vector<int>& nums) {
        int size = nums.size(), ballance = size, max_len = 0;
        int ballances[size * 2 + 1] = {};
        for (auto i = 0; i < size; ++i) {
            ballance += nums[i] == 0 ? -1 : 1;
            if (ballance == size) max_len = i + 1;
            else {
                if (ballances[ballance] != 0) max_len = max(max_len, i - ballances[ballance] + 1);
                else ballances[ballance] = i + 1;
            }
        }
        return max_len;
    }
    

  • 3

    Could define perfect balance as ballance == size, then you wouldn't need the + size.


  • 0
    V

    @StefanPochmann Cool, updated the code and description.


  • 0
    D
    This post is deleted!

  • 0
    D
    if (ballances[ballance] != 0) 
        max_len = max(max_len, i - ballances[ballance] + 1);
    else 
        ballances[ballance] = i + 1;
    

    if you write

    ballances[ballance] = i;
    

    it should be okay

    max_len = max(max_len, i - ballances[ballance]);
    

  • 0
    W

    @wdw828
    you can do it, but you should initialize the ballances like
    vector<int> ballances(size*2+1,-1);


  • 0

    C# - I ran both to see if this was significant. And the OJ results are so inconsistent that it was hard to say for sure, although it did seem the array version was slightly faster. The array version has to be faster but also uses more memory so not sure overall which is better.

        public int FindMaxLength(int[] nums)
        {
            int[] map = new int[2 * (nums.Length + 1)];
            int mid = map.Length / 2;
            
            int max = 0;
            int delta = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                delta += nums[i] == 0 ? -1 : 1;
                if (delta == 0)
                {
                    max = i + 1;
                }
                else if (map[mid + delta] == 0)
                {
                    map[mid + delta] = i + 1; // use 0 as not-set
                }
                else if (max < i + 1 - map[mid + delta])
                {
                    max = i + 1 - map[mid + delta];
                }
            }
            return max;
        }
    

    with Map

        public int FindMaxLength(int[] nums)
        {
            Dictionary<int,int> map = new Dictionary<int,int>();
            
            int max = 0;
            int delta = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                delta += nums[i] == 0 ? -1 : 1;
                if (delta == 0)
                {
                    max = i + 1;
                }
                else if (!map.ContainsKey(delta))
                {
                    map[delta] = i;
                }
                else if (max < i - map[delta])
                {
                    max = i - map[delta];
                }
            }
            return max;
        }
    

  • 0
    J
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.