# Easy Java O(n) Solution, PreSum + HashMap

• 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;
}
}
``````

• 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;
}
}
``````

• Similar idea to solve LC 325 :

Maximum Size Subarray Sum Equals k

• Your idea is so brilliant!!!

• This post is deleted!

• Can you please explain me how this logic works

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

• 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;
}

``````

• @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)`.

• 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;
}
``````

• @shawngao

Inspiring.

• very smart to set zeroes to minus one

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

• "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,.

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);
}
``````

• @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.

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.

``````-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.

• Really cool solution

• @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;
}
``````

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

• Could you explain why the map should be initialized as

``````sumToIndex.put(0, -1);
``````

?

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