525. Contiguous Array
https://leetcode.com/problems/contiguous-array/
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.
---
Intuition
Similar to prefix sum array, consider a running difference of zeros, ones
Traverse left to right, count zeros, ones, and compute diff at each index position
If diff at any two indexes is the same, => the net effect of subarray between those two indices is 0, => difference between zeros, and ones is 0 => equal number of zeros, and ones between those two indices
Capture the difference, and index at which this occurs in a Hash Map
Seed the map with key = 0, value = -1 => diff 0 occurs at index -1
Traverse the array left to right
At each index i, compute running diff
If map contains current diff
=> ans = max (ans, i - previous index at which same diff occurs) => max(ans, i - map(diff)
else
=> map.put(current diff, i)
*Since map is seeded with 0, -1, we can compute ans = max (ans, i - map(diff)) , not need for + 1 difference of indices
--
Time - O(n)
Space - O(n)
---
Intuition
Similar to prefix sum array, consider a running difference of zeros, ones
Traverse left to right, count zeros, ones, and compute diff at each index position
If diff at any two indexes is the same, => the net effect of subarray between those two indices is 0, => difference between zeros, and ones is 0 => equal number of zeros, and ones between those two indices
Capture the difference, and index at which this occurs in a Hash Map
Seed the map with key = 0, value = -1 => diff 0 occurs at index -1
Traverse the array left to right
At each index i, compute running diff
If map contains current diff
=> ans = max (ans, i - previous index at which same diff occurs) => max(ans, i - map(diff)
else
=> map.put(current diff, i)
*Since map is seeded with 0, -1, we can compute ans = max (ans, i - map(diff)) , not need for + 1 difference of indices
--
Time - O(n)
Space - O(n)
---
