Contiguous Array

Med

#0510Time: 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`.1 company

Patterns

Prefix Sum

Data structures

Array Hash Table

Companies

Morgan Stanley

Prompt

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 <= 10⁵
nums[i] is either 0 or 1.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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

1java\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

Complexity

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

Trade-offs

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

This is an efficient approach that solves the problem in a single pass. The core idea is to reframe the problem: if we treat 0s as -1s, 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.

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.

Walkthrough

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

1java\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

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int findMaxLength(int[] nums) {4    Map<Integer, Integer> mp = new HashMap<>();5    mp.put(0, -1);6    int s = 0, ans = 0;7    for (int i = 0; i < nums.length; ++i) {8      s += nums[i] == 1 ? 1 : -1;9      if (mp.containsKey(s)) {10        ans = Math.max(ans, i - mp.get(s));11      } else {12        mp.put(s, i);13      }14    }15    return ans;16  }17}

1/** * @param {number[]} nums * @return {number} */ var findMaxLength =2  function (nums) {3    const mp = new Map();4    mp.set(0, -1);5    let s = 0;6    let ans = 0;7    for (let i = 0; i < nums.length; ++i) {8      s += nums[i] == 0 ? -1 : 1;9      if (mp.has(s)) ans = Math.max(ans, i - mp.get(s));10      else mp.set(s, i);11    }12    return ans;13  };

1class Solution {2public:3  int findMaxLength(vector<int> &nums) {4    unordered_map<int, int> mp;5    int s = 0, ans = 0;6    mp[0] = -1;7    for (int i = 0; i < nums.size(); ++i) {8      s += nums[i] == 1 ? 1 : -1;9      if (mp.count(s))10        ans = max(ans, i - mp[s]);11      else12        mp[s] = i;13    }14    return ans;15  }16};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem