# Contiguous Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/contiguous-array)
Canonical: https://scaleengineer.com/dsa/problems/contiguous-array
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## 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.

**Example 3:**

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

**Constraints:**

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

# Approaches
## Brute Force Approach
This approach involves checking every possible contiguous subarray within the given array. For each subarray, we count the number of zeros and ones. If they are equal, we check if the current subarray's length is greater than the maximum length found so far and update it if necessary.
**Time:** O(n^2), where `n` is the number of elements in the `nums` array. The two nested loops lead to a quadratic runtime. · **Space:** O(1), as we only use a constant amount of extra space for variables like `maxLength`, `zeros`, and `ones`.
**Pros:** Simple to understand and implement.; Requires no extra space besides a few variables for counting.
**Cons:** Very inefficient with a time complexity of O(n^2).; Will likely result in a 'Time Limit Exceeded' (TLE) error for large input sizes as specified in the constraints (n <= 10^5).
### Explanation
We can find the solution by considering every possible contiguous subarray. This can be done using two nested loops. The outer loop fixes the starting point of the subarray, and the inner loop fixes the ending point.\n\nFor each subarray defined by a start and end index, we can count the number of 0s and 1s. If these counts are equal, it means we've found a valid subarray. We then compare its length with the maximum length found so far and update the maximum if the current subarray is longer.\n\nTo make this slightly more efficient, as we extend the subarray in the inner loop (by moving the end pointer), we can maintain the counts of 0s and 1s incrementally instead of recounting for each subarray.\n\nHere is the implementation:\n```java\nclass Solution {\n    public int findMaxLength(int[] nums) {\n        int maxLength = 0;\n        for (int i = 0; i < nums.length; i++) {\n            int zeros = 0;\n            int ones = 0;\n            for (int j = i; j < nums.length; j++) {\n                if (nums[j] == 0) {\n                    zeros++;\n                } else {\n                    ones++;\n                }\n                if (zeros == ones) {\n                    maxLength = Math.max(maxLength, j - i + 1);\n                }\n            }\n        }\n        return maxLength;\n    }\n}\n```
### Algorithm
- Initialize a variable `maxLength` to 0.
- Iterate through the array with a starting index `i` from 0 to `n-1`.
- For each `i`, start an inner loop with an ending index `j` from `i` to `n-1`.
- Inside the inner loop, maintain counts of zeros and ones for the subarray `nums[i...j]`.
- If the count of zeros equals the count of ones, update `maxLength = max(maxLength, j - i + 1)`.
- After the loops complete, return `maxLength`.

## Using HashMap and Prefix Sum
This is an efficient approach that solves the problem in a single pass. The core idea is to reframe the problem: if we treat `0`s as `-1`s, we are looking for the longest contiguous subarray that sums to 0. We can find this by tracking the cumulative sum (prefix sum) and using a HashMap to store the first index at which each cumulative sum occurs.
**Time:** O(n), where `n` is the length of the `nums` array. We iterate through the array only once. · **Space:** O(n), where `n` is the length of the `nums` array. In the worst-case scenario, the hash map might store up to `n` distinct cumulative sum values if all prefix sums are unique.
**Pros:** Highly efficient with a linear time complexity.; Solves the problem in a single pass through the array.
**Cons:** Requires extra space for the HashMap, which can be up to O(n) in the worst case.
### Explanation
The problem of finding a contiguous subarray with an equal number of 0s and 1s can be cleverly transformed. If we replace every 0 in the array with -1, the problem becomes finding the longest contiguous subarray with a sum of 0.\n\nThis new problem can be solved efficiently using a hash map and the concept of prefix sums. We iterate through the (conceptually) transformed array, calculating a running sum (let's call it `count`).\n\nWe use a `HashMap` to store the first index at which a particular `count` is seen. The map will store `(count, index)` pairs.\n\nIf we encounter a `count` that we have seen before at an earlier index `j`, it means the sum of the elements between index `j` and the current index `i` is 0. The length of this subarray is `i - j`. We want to maximize this length. To do so, for any given `count`, we only care about the first time it appeared.\n\nA special case to handle is when a valid subarray starts from the very beginning (index 0). To account for this, we initialize our map with the entry `(0, -1)`. This way, if the cumulative sum up to index `i` is 0, the length is correctly calculated as `i - (-1) = i + 1`.\n\nHere is the implementation:\n```java\nimport java.util.HashMap;\nimport java.util.Map;\n\nclass Solution {\n    public int findMaxLength(int[] nums) {\n        Map<Integer, Integer> map = new HashMap<>();\n        map.put(0, -1); // To handle subarrays starting from index 0\n        int maxLength = 0;\n        int count = 0;\n\n        for (int i = 0; i < nums.length; i++) {\n            count = count + (nums[i] == 1 ? 1 : -1);\n\n            if (map.containsKey(count)) {\n                maxLength = Math.max(maxLength, i - map.get(count));\n            } else {\n                map.put(count, i);\n            }\n        }\n        return maxLength;\n    }\n}\n```
### Algorithm
- Initialize a `HashMap` called `map` to store `(cumulative_sum, index)` pairs.\n- Add an initial entry `(0, -1)` to the `map` to correctly handle subarrays that start from index 0.\n- Initialize `maxLength = 0` and `count = 0` (our running sum).\n- Iterate through the input array `nums` from `i = 0` to `n-1`:\n  - Update `count`: increment by 1 if `nums[i]` is 1, and decrement by 1 if `nums[i]` is 0.\n  - Check if `count` already exists as a key in `map`:\n    - If yes, it means a subarray with sum 0 exists between the previous index of this `count` and the current index `i`. Calculate the length `i - map.get(count)` and update `maxLength` if this length is greater.\n    - If no, add the current `count` and its index `i` to the map: `map.put(count, i)`.\n- After the loop, return `maxLength`.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var findMaxLength =
  function (nums) {
    const mp = new Map();
    mp.set(0, -1);
    let s = 0;
    let ans = 0;
    for (let i = 0; i < nums.length; ++i) {
      s += nums[i] == 0 ? -1 : 1;
      if (mp.has(s)) ans = Math.max(ans, i - mp.get(s));
      else mp.set(s, i);
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int findMaxLength(vector<int> &nums) {
    unordered_map<int, int> mp;
    int s = 0, ans = 0;
    mp[0] = -1;
    for (int i = 0; i < nums.size(); ++i) {
      s += nums[i] == 1 ? 1 : -1;
      if (mp.count(s))
        ans = max(ans, i - mp[s]);
      else
        mp[s] = i;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findMaxLength(self, nums: List[int]) -> int: s = ans = 0 mp = {0: - 1} for i, v in enumerate(nums): s += 1 if v == 1 else - 1 if s in mp: ans = max(ans, i - mp[s]) else: mp[s] = i return ans

```