Contiguous Array
MedPrompt
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.Example 3:
Input: nums = [0,1,1,1,1,1,0,0,0]
Output: 6
Explanation: [1,1,1,0,0,0] is the longest contiguous subarray with equal number of 0 and 1.
Constraints:
1 <= nums.length <= 105nums[i]is either0or1.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves checking every possible contiguous subarray within the given array. For each subarray, we count the number of zeros and ones. If they are equal, we check if the current subarray's length is greater than the maximum length found so far and update it if necessary.
Algorithm
- Initialize a variable
maxLengthto 0. - Iterate through the array with a starting index
ifrom 0 ton-1. - For each
i, start an inner loop with an ending indexjfromiton-1. - Inside the inner loop, maintain counts of zeros and ones for the subarray
nums[i...j]. - If the count of zeros equals the count of ones, update
maxLength = max(maxLength, j - i + 1). - After the loops complete, return
maxLength.
Walkthrough
We can find the solution by considering every possible contiguous subarray. This can be done using two nested loops. The outer loop fixes the starting point of the subarray, and the inner loop fixes the ending point.\n\nFor each subarray defined by a start and end index, we can count the number of 0s and 1s. If these counts are equal, it means we've found a valid subarray. We then compare its length with the maximum length found so far and update the maximum if the current subarray is longer.\n\nTo make this slightly more efficient, as we extend the subarray in the inner loop (by moving the end pointer), we can maintain the counts of 0s and 1s incrementally instead of recounting for each subarray.\n\nHere is the implementation:\njava\nclass Solution {\n public int findMaxLength(int[] nums) {\n int maxLength = 0;\n for (int i = 0; i < nums.length; i++) {\n int zeros = 0;\n int ones = 0;\n for (int j = i; j < nums.length; j++) {\n if (nums[j] == 0) {\n zeros++;\n } else {\n ones++;\n }\n if (zeros == ones) {\n maxLength = Math.max(maxLength, j - i + 1);\n }\n }\n }\n return maxLength;\n }\n}\n
Complexity
Time
O(n^2), where `n` is the number of elements in the `nums` array. The two nested loops lead to a quadratic runtime.
Space
O(1), as we only use a constant amount of extra space for variables like `maxLength`, `zeros`, and `ones`.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space besides a few variables for counting.
Cons
Very inefficient with a time complexity of O(n^2).
Will likely result in a 'Time Limit Exceeded' (TLE) error for large input sizes as specified in the constraints (n <= 10^5).
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.