Contiguous Array

Problem

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Constraints:

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

Source: Leetcode 525. Contiguous Array

Solution

The Idea

The idea to solve this problem is similar to what we have done solving problem Maximum size subarray sum equals k. If you did not solve that problem and also do not want to read that post now, here is a recap of the idea in context of this current problem.

We need to find the maximum length of a subarray which will have equal number of zeros and ones. What if we use a counter (in a loop going through the array) which will be incremented by 1 when we will find a one and will be decremented by 1 when we will find a zero?

This way, when the counter is 0, we know that we have got equal number of zeros and ones so far.

But we can know the equal zeros and ones are found using other values of counter as well!

Say at some arbitrary point at index1, our counter value was 3. Then we continue moving forward and updating the counter. Now, say, later at some point at index2 we again found counter = 3!

So, at index1 we had counter = 3 which means we counted 3 more ones than zeros so far and at index2 we also have 3 more ones than zeros so far (because counter = 3 again). Right?

This means the 3 ones at index1 had to decrease by 3 zeros and again increased by a new set of 3 ones when reached at index2.

In other words, between index1 and index2, we have seen equal number of zeros and ones!

A pictures tells a thousand words.

Henrik Ibsen

Let’s examine the image below and try to visualize the idea.

At index1 (index value 2), we have counter = 3, because as you see, the previous 3 ones made our counter = 3. Now we move forward and found a 0, so we decrease counter = counter – 1 = 2. We move forward and decrease counter again for finding another zero. At index value 6, we find one again and increase counter by 1. That’s how we move forward and finally reach at index value 8 where we find again counter = 3!

If you see carefully, we get equal number of zeros and ones not only between index value 2 and 8, but also between index 3 and 7and between index 4 and 6. Among these findings, we have to save the maximum length of the subarray with equal zeros and ones.

But, how do we know that a counter found at some point was found before and in which index it was found before?

Detail Explanation

The answer is, we can use a map to hold our counter values and the corresponding index values. If a counter is not in the map, we will take that counter and keep the index associated with that counter in the map. If a counter is already found in the map at some later index, we will simply subtract the index of the map from the current index.

But what if the there are equal zeros and ones and we found counter = 0? We can save this counter for future but what if we do not get any equal zeros and ones anymore?

To solve this problem, we will initialize our map with 0 and an imaginary index -1. Say at index 3 we found counter = 0. Then the array length of equal zeros and ones will be 3 – index where counter was 0 = 3 – (1) = 4!

Hope the explanation was understood.

Now let’s go to the detail step by step explanation of the algorithm.

Let’s say we have an array like below. We have variable count = 0 as our counter, a map count_last_seen initialized like count_last_seen[ 0 ] = -1 and a variable ans = 0 to keep the maximum length.

At i = 0, there is a 0, so we make count = 0 – 1 = -1 and update our map.

At i = 1, there is a 1, so we make count = -1 + 1 = 0. This 0 was seen before and in the map. So, we calculate the length and update ans.

At i = 2, there is a 1, so we make count = 0 + 1 = 1 and update our map.

At i = 3, there is a 1, so we make count = 1 + 1 = 2 and update our map.

At i = 4, there is a 0, so we make count = 2 – 1 = 1. This 1 was seen before and in the map. So, we calculate the length and update ans.

At i = 5, there is a 0, so we make count = 1 – 1 = 0. This 0 was seen before and in the map. So, we calculate the length and update ans.

At i = 6, there is a 1, so we make count = 0 + 1 = 1. This 1 was seen before and in the map. So, we calculate the length and update ans.

This is how we can continue and finally get the maximum length saved in ans.

We would highly recommend you continue this process and write down the answer in comment box! 🙂 Then try to code it yourself. If you don’t get it, only after trying check the code below.

Code

C++

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        map<int, int> count_last_seen;
        int ans = 0;
        int count = 0;
        count_last_seen[0] = -1;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] == 1) count++;
            else count--;
            if(count_last_seen.find(count) == count_last_seen.end())
                count_last_seen[ count ] = i;
            else
                ans = max(ans, i - count_last_seen[ count ]);
        }
        return ans;
    }
};

Conclusion

Hope you enjoyed this post. If you find it’s too long or too much expressive, please write down your comment. We will improve it further.

Happy coding! 🙂