525

525. Contiguous Array (Medium)

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.

Companies:
Google, Facebook, Amazon

Related Topics:
Array, Hash Table, Prefix Sum

Similar Questions:

• Maximum Size Subarray Sum Equals k (Medium)

Solution 1. Prefix State Map

Replace all 0s with -1s, and now the question becomes finding the longest contiguous array that sums up to 0.

Use unordered_map<int, int> m to store the mapping between the running sum and the index of its first occurrence. m initially holds { 0, -1 } which means a pseudo running sum 0 at index -1.

For each running sum,

• if it's the first occurrence, store the mapping -- m[sum] = i
• otherwise, update ans with max(ans, i - m[sum]).

// OJ: https://leetcode.com/problems/contiguous-array
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/79906/easy-java-o-n-solution-presum-hashmap/
class Solution {
public:
    int findMaxLength(vector<int>& A) {
        unordered_map<int, int> m{{0,-1}};
        int ans = 0;
        for (int i = 0, sum = 0; i < A.size(); ++i) {
            sum += A[i] ? 1 : -1;
            if (m.count(sum)) ans = max(ans, i - m[sum]);
            else m[sum] = i;
        }
        return ans;
    }
};