Contiguous Array

MEDIUM

Description

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

Checkout 2 different approaches to solve Contiguous Array. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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:\njava\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 Analysis

Time Complexity: O(n^2), where `n` is the number of elements in the `nums` array. The two nested loops lead to a quadratic runtime.Space Complexity: O(1), as we only use a constant amount of extra space for variables like `maxLength`, `zeros`, and `ones`.

Pros and Cons

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

Code Solutions

Checking out 4 solutions in different languages for Contiguous Array. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Contiguous Array

Patterns:

Prefix Sum

Data Structures:

ArrayHash Table

Companies:

Morgan Stanley |