# Contiguous Array LeetCode Solution

Difficulty Level Medium

## Problem Statement

Contiguous Array LeetCode Solution – Given a binary array `nums`, return the maximum length of a contiguous subarray with an equal number of `0` and `1`.

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

## Explanation

Now what we will do is, convert all the “0” to “-1” in the example, so we get something like:- [1, -1-1, 1, -1, 1, 1]. If you see this, the problem is somewhat like returning the longest subarray length whose sum is “ZERO”
Because equal no. of 1’s & 0’s, so we had replaced 0 with -1. So, that means the same as well there will be equal no. of 1 & -1.

That’s the thing if in any subarray there is an equal no. of 1 & -1 their sum will be 0. We have to return that subarray length, whose sum is 0. And we have to find the longest subarray.

Let’s just see how we will solve this problem using HashMap.
We will use the help of cumulative sum, which means what is the sum from the 0th index to the 6th index. Using this cumulative sum, we will solve this problem in O(N).
In our hashMap, we will have key & value.

• Initially let’s assume our gain is 0 & we are standing at an index of -1
• We move forward and get a gain of 1. And in our hashmap for reference, we put key 0 -> -1 value. Why this, because initially we are at no-where & our gain is 0 & our final answer is 0 at index -1`Just hold on you will understand`
• At index 0 we get 1. And if we look in our HashMap, do we have key-value pair for 1? No, then we will create key 1 -> 0 value pair in hashmap. `Our cumulative sum is 0 + 1 = 1`
• Now moving to index 1 we get a gain of -1 & loss of 1. Now our gain becomes 0 because `Our cumulative sum is 1 + (-1) = 0` so what does it represent is in the Journey from -1th index to 1st index, we found a subarray i.e. [1, 0]. The subarray has equal no. of 0s & 1s. Now to calculate its length we started the journey from index -1 to index 1. `Thus, 1 - (-1) = 2`.
• So, to trace this 2 we put our initial key 0 & value -1Now hope you got an idea a bit, anyways. We will update it’s `current & final-ans with 2`
• Now moving further & at index 2 we got a gain of -1 as `Our cumulative sum is 0 + (-1) = -1` And if we look at hashmap -1 is not present we will make key-value pair of -1 -> 2.
• Now moving further & at index 3 we get 1 & our gain becomes 0 as `Our cumulative sum is 1 + (-1) = 0`. And if we look at the hashmap 0 is present with a value of -1. Now to calculate its length we started the journey from index 2 to index 3. `Thus, 3 - (-1) = 4`, then update our `current & final-ans with 4` And Till now we have found a subarray of size 4
• Now moving further & at index 4 we got a gain of -1 as `Our cumulative sum is 0 + (-1) = -1`. And if we look at the hashmap -1 is present at the key-value pair of -1 -> 2. We got one more subarray in the Journey from the 3rd index to the 4th index. But, if we calculate its length, it will be `4 - (+2) = 2` & update our current with 2 and compare with final-ans i.e. 4 which is less, we will not consider it.
• Now moving further & at index 5 we get 1 & our gain becomes 0 as `Our cumulative sum is 1 + (-1) = 0`. We got one more subarray in the Journey from the 4th index to the 5th index. calculate its length, it will be `5 - (-1) = 6`, then update our `current & final-ans with 6`.
• Finally moving at index 6th, we get 1 & our gain becomes 1 as `Our cumulative sum is 0 + 1 = 1` . And if we look at the hashmap 1 is present at the key-value pair of 1 -> 0. We got one more subarray in the Journey from the 5th index to the 6th index. As we calculate its length, it will be `6 - (0) = 6` & compare with current & final-ans i.e. 6 which is equal to it.
• In the end, we get 2 big subarrays having equal no. of 1s & 0s
• [1,0,0,1,0,1]
• [0,0,1,0,1,1]

## Code

### Java Code for Contiguous Subarray

```class Solution {
public int findMaxLength(int[] nums) {
if (nums == null || nums.length == 0) { // Base Case
return 0;
}
// Converting all 0 to -1
for(int i = 0; i < nums.length; i++){
if(nums[i] == 0) nums[i] = -1;
}
int sum = 0; // current
int max = 0; // final-ans
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // put reference in the starting of 0 & -1, as i have tell you in the starting
for(int i = 0; i < nums.length; i++){
sum += nums[i]; // cumulative sum
if(map.containsKey(sum)){ // if cumulative sum key :- 0, -1, 1 already present
int last = map.get(sum); // we get it's value
max = Math.max(max, i - last); // and update max
}
else{ // if it's not present then create it's key-value pair
map.put(sum, i);
}
}
return max; // finally return it
}
}```

### C++ Code for Contiguous Subarray

```class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int,int> mp; //map of <gain,index> form
mp=-1; //add starting index with default gain of 0 at -1
//change all zeros to -1
for(int i=0;i<nums.size();i++){
nums[i]==0?nums[i]=-1:nums[i]=1;
}
int sum=0,res=0;
for(int i=0;i<nums.size();i++){
//cumulative sum
sum+=nums[i];

//check if value already exists in the map
if(mp.find(sum)!=mp.end()){
//finding the length of possible subarray and comparing with the max result
res=max(res,i-mp[sum]);
}
else{
mp[sum]=i;
}
}
return res;
}
};```

### Python Code for Contiguous Subarray

```class Solution(object):
def findMaxLength(self, nums):
count = 0
max_length=0
table = {0: 0}
for index, num in enumerate(nums, 1):
if num == 0:
count -= 1
else:
count += 1

if count in table:
max_length = max(max_length, index - table[count])
else:
table[count] = index

return max_length```

O(N)

O(N)

Translate »