Welcome to Subscribe On Youtube
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
answithmax(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;
}
};
-
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; } } ############ 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; } } -
// 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: 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 ############ 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 -
func findMaxLength(nums []int) int { mp := map[int]int{0: -1} s, ans := 0, 0 for i, v := range nums { if v == 0 { v = -1 } s += v if j, ok := mp[s]; ok { ans = max(ans, i-j) } else { mp[s] = i } } return ans } func max(a, b int) int { if a > b { return a } return b } -
/** * @param {number[]} nums * @return {number} */ var findMaxLength = function (nums) { const mp = new Map(); mp.set(0, -1); let s = 0; let ans = 0; for (let i = 0; i < nums.length; ++i) { s += nums[i] == 0 ? -1 : 1; if (mp.has(s)) ans = Math.max(ans, i - mp.get(s)); else mp.set(s, i); } return ans; };