Easy Java O(n) Solution, PreSum + HashMap


  • 84

    The idea is to change 0 in the original array to -1. Thus, if we find SUM[i, j] == 0 then we know there are even number of -1 and 1 between index i and j. Also put the sum to index mapping to a HashMap to make search faster.

    public class Solution {
        public int findMaxLength(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == 0) nums[i] = -1;
            }
            
            Map<Integer, Integer> sumToIndex = new HashMap<>();
            sumToIndex.put(0, -1);
            int sum = 0, max = 0;
            
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                if (sumToIndex.containsKey(sum)) {
                    max = Math.max(max, i - sumToIndex.get(sum));
                }
                else {
                    sumToIndex.put(sum, i);
                }
            }
            
            return max;
        }
    }
    

  • 4

    same idea

    public class Solution {
        public int findMaxLength(int[] nums) {
            int[] cnt = new int[nums.length];
            for(int i = 0; i<nums.length; i++){
                if(i>0) cnt[i] = cnt[i-1];
                if(nums[i]==1) cnt[i]++;
                else cnt[i]--; 
            }
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, -1);
            int max = 0; 
            for(int i = 0; i<cnt.length; i++){
                if(map.containsKey(cnt[i])) max = Math.max(max, i - map.get(cnt[i]));
                if(!map.containsKey(cnt[i])) map.put(cnt[i], i);
            }
            return max; 
        }
    }
    

  • 4
    Z

    Similar idea to solve LC 325 :

    Maximum Size Subarray Sum Equals k


  • 0
    D

    Your idea is so brilliant!!!


  • 0
    P
    This post is deleted!

  • 0
    P

    Can you please explain me how this logic works

    Math.max(max, i - sumToIndex.get(sum))


  • 1

    I had a similar idea, but in one pass:

        public int findMaxLength(int[] nums) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>() {{put(0,0);}};
            int maxLength = 0, runningSum = 0;
            for (int i=0;i<nums.length;i++) {
                runningSum += nums[i];
                Integer prev = map.get(2*runningSum-i-1);
                if (prev != null) maxLength = Math.max(maxLength, i+1-prev);
                else map.put(2*runningSum-i-1, i+1);
            }
            return maxLength;
        }
    
    

  • 5

    @priya.k7059
    Let me try to explain shawngao's idea more clearly. sumToIndex is a hash table stores the accumulative total's corresponding index. If and only if we find two different indices i, j and the two corresponding sum sumToIndex[sum]for i, j are equal, we claim that sum(nums[j+1:i+1]) == 0.

    Consider sumToIndex.get(sum) as j, we wanna update answer with j - i which is exactly i - sumToIndex.get(sum).


  • 0

    nice solution, here I just add to sum -1 if the element is zero rather than initialize my array with the zero for -1 replacement.

        public int FindMaxLength(int[] nums) 
        {
            Dictionary<int,int> map = new Dictionary<int,int>();
            int delta = 0, max = 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)) max = Math.Max(max, i - map[delta]);
                else map[delta] = i;
            }
            return max;
        }
    

  • 0

    @shawngao

    Inspiring.


  • 0
    W

    very smart to set zeroes to minus one


  • 0
    I

    @shawngao sum += nums[i] * 2 - 1;


  • 0
    P

    "SUM[i, j] == 0 then we know there are even number of -1 and 1 between index i and j". This makes sense to me. However I noticed we are storing the sum regardless of its value on the map. And we also calculate the max length everytime we see the same sum twice. For eg:
    [0,0,1,0,0,0,1,1] the max length 6 is actually returned on the stored sum value -2. I know I am likely missing something obvious here, but I'd really appreciate it if someone could point it out,.


  • 0

    @pradyot.dhulipala

    However I noticed we are storing the sum regardless of its value on the map.

    This is not true. We only save a sum at the first time we see it. Meaning, the left-most one, which guarantee we have the longest result. Later when we see that sum again, we just calculate the distance.

                if (sumToIndex.containsKey(sum)) {
                    max = Math.max(max, i - sumToIndex.get(sum));
                }
                else {
                    sumToIndex.put(sum, i);
                }
    

  • 0
    P

    @shawngao Thanks for the response. What i meant with the stmt, was that we are storing the sum whatever it might be. Since its a map... i get that we are only storing once. But my question, and I could have been clearer was How does a particular sum value -2 in my example indicate an even number of 0's and 1's. I would assume that a sum == 0 would indicate that. Again the program clearly works, its just a gap in my understanding that I am trying to fill.


  • 5

    @pradyot.dhulipala

    But my question was How does a particular sum value -2 in my example indicate an even number of 0's and 1's. I would assume that a sum == 0 would indicate that.

    That's because the underlying characteristic of the PreSum array. PreSum[i] = Sum(nums[0], nums[1], ..., nums[i]). Thus, if PreSum[j] - PreSum[i] = 0 = Sum(nums[i + 1], nums[i + 2], ..., nums[j]), we know between index i + 1 and j, there are even numbers of 1 and -1.

    In your example:

    -1,-1, 1,-1,-1,-1, 1, 1    <- Transformed input 
    -1,-2,-1,-2,-3,-4,-3,-2    <- PreSum array
    

    There are 6 elements between the first -2 and last -2, indicating sum of those 6 elements is 0. Thus there are even numbers of 1 and -1.


  • 0
    H

    Really cool solution


  • 0

    @zzwcsong You're absolutely right! Once the transformation is done to flip 0 to -1, it's really easy provided you know how to solve that problem :) Here's my solution:

    public int findMaxLength(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) nums[i] = -1;
        }
        return maxSizeSubarrayWithSumK(nums, 0);
    }
    
    private int maxSizeSubarrayWithSumK(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int sum = 0, max = 0;
        for(int i = 0; i < nums.length; i++) {
           sum += nums[i];
           int delta = sum - k;
           if (delta == 0) {
           	max = i + 1;
           } else if (map.containsKey(delta)) {
           	max = Math.max(max, i - map.get(delta));
           }
           if (!map.containsKey(sum)) map.put(sum, i);
        }
        return max;
    }
    

  • 0
    R

    @shawngao this is a neatest explanation you can get ! . thanks a lot


  • 4
    O

    Could you explain why the map should be initialized as

    sumToIndex.put(0, -1);
    

    ?


Log in to reply
 

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