Skip to content

525. Contiguous Array

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.

 

Constraints:

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

Solutions

Solution 1: Prefix Sum + Hash Table

According to the problem description, we can treat \(0\)s in the array as \(-1\). In this way, when encountering a \(0\), the prefix sum \(s\) will decrease by one, and when encountering a \(1\), the prefix sum \(s\) will increase by one. Therefore, suppose the prefix sum \(s\) is equal at indices \(j\) and \(i\), where \(j < i\), then the subarray from index \(j + 1\) to \(i\) has an equal number of \(0\)s and \(1\)s.

We use a hash table to store all prefix sums and their first occurrence indices. Initially, we map the prefix sum of \(0\) to \(-1\).

As we iterate through the array, we calculate the prefix sum \(s\). If \(s\) is already in the hash table, then we have found a subarray with a sum of \(0\), and its length is \(i - d[s]\), where \(d[s]\) is the index where \(s\) first appeared in the hash table. If \(s\) is not in the hash table, we store \(s\) and its index \(i\) in the hash table.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        d = {0: -1}
        ans = s = 0
        for i, x in enumerate(nums):
            s += 1 if x else -1
            if s in d:
                ans = max(ans, i - d[s])
            else:
                d[s] = i
        return ans

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func findMaxLength(nums []int) int {
    d := map[int]int{0: -1}
    ans, s := 0, 0
    for i, x := range nums {
        if x == 0 {
            x = -1
        }
        s += x
        if j, ok := d[s]; ok {
            ans = max(ans, i-j)
        } else {
            d[s] = i
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function findMaxLength(nums: number[]): number {
    const d: Record<number, number> = { 0: -1 };
    let ans = 0;
    let s = 0;
    for (let i = 0; i < nums.length; ++i) {
        s += nums[i] ? 1 : -1;
        if (d.hasOwnProperty(s)) {
            ans = Math.max(ans, i - d[s]);
        } else {
            d[s] = i;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxLength = function (nums) {
    const d = { 0: -1 };
    let ans = 0;
    let s = 0;
    for (let i = 0; i < nums.length; ++i) {
        s += nums[i] ? 1 : -1;
        if (d.hasOwnProperty(s)) {
            ans = Math.max(ans, i - d[s]);
        } else {
            d[s] = i;
        }
    }
    return ans;
};

Comments