Formatted question description: https://leetcode.ca/all/525.html

525. Contiguous Array (Medium)

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

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

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

Solution 1.

Let dp[i + 1] := the max length of contiguous array ending at index i.

Given start = i - dp[i], nums from nums[start] to nums[i - 1] forms a contiguous array.

If nums[start - 1] != nums[i], dp[i + 1] can be constructed using dp[i] + 2 + dp[start - 1]. The DP array saves computation in this case, but if nums[start - 1] == nums[i] I have to do linear search.

The search direction should be rightward. Assume nums[start - 1] = nums[i] = 1, If there are two zeroes can help form a longer contiguous array at the left of nums[start - 1], it’s contradicts with the fact that nums[start] ... nums[i - 1] is the longest contiguous array ending at i - 1 since nums[start - 2] ... nums[i - 1] is contiguous and even longer.

        v     v
... 0 0 1 ... 1

When search rightward from start, use int diff = 0 to denote the difference between 0 and 1. If nums[start] == nums[i], increment diff; otherwise decrement diff. When diff == 1, breaks the iteration because it means one more number same as nums[i] are popped.

// OJ: https://leetcode.com/problems/contiguous-array
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
  int findMaxLength(vector<int>& nums) {
    vector<int> dp(nums.size() + 1, 0);
    int ans = 0;
    for (int i = 0; i < nums.size(); ++i) {
      int start = i - dp[i];
      if (start > 0 && nums[start - 1] != nums[i]) {
        dp[i + 1] = dp[i] + 2 + dp[start - 1];
      } else {
        for (int diff = 0; start <= i && diff != 1; ++start) {
          if (nums[start] == nums[i]) diff++;
          else diff--;
        }
        dp[i + 1] = i - start + 1;
      }
      ans = max(ans, dp[i + 1]);
    }
    return ans;
  }
};

Solution 2.

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
// 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>& nums) {
        unordered_map<int, int> m{ {0, -1} };
        int N = nums.size(), sum = 0, ans = 0;
        for (int i = 0; i < N; ++i) {
            sum += nums[i] ? 1 : -1;
            if (m.count(sum)) ans = max(ans, i - m[sum]);
            else m[sum] = i;
        }
        return ans;
    }
};

Java

  • class Solution {
        public int findMaxLength(int[] nums) {
            if (nums == null || nums.length == 0)
                return 0;
            int length = nums.length;
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            int maxLength = 0;
            int counter = 0;
            for (int i = 0; i < length; i++) {
                int num = nums[i] == 1 ? 1 : -1;
                counter += num;
                if (counter == 0)
                    maxLength = i + 1;
                else {
                    if (map.containsKey(counter)) {
                        int prevIndex = map.get(counter);
                        int curLength = i - prevIndex;
                        maxLength = Math.max(maxLength, curLength);
                    }
                }
                if (!map.containsKey(counter))
                    map.put(counter, i);
            }
            return maxLength;
        }
    }
    
  • // OJ: https://leetcode.com/problems/contiguous-array
    // 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;
        }
    };
    
  • class Solution(object):
      def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        d = {0: -1}
        count = ans = 0
        delta = {1: -1, 0: 1}
        for i in range(len(nums)):
          count += delta.get(nums[i], 0)
          if count in d:
            ans = max(ans, i - d[count])
          else:
            d[count] = i
        return ans
    
    

All Problems

All Solutions