grid47 Exploring patterns and algorithms
Sep 15, 2024
6 min read
Solution to LeetCode 525: Contiguous Array Problem
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.
Problem
Approach
Steps
Complexity
Input: The input consists of a binary array of integers nums, where each element is either 0 or 1.
Example: nums = [1, 0, 1, 0]
Constraints:
• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.
Output: Return the maximum length of a contiguous subarray with an equal number of 0s and 1s.
Example: 4
Constraints:
• The output is an integer.
Goal: The goal is to find the length of the longest contiguous subarray that has an equal number of 0s and 1s.
Steps:
• 1. Use a score to track the difference between the count of 1s and 0s.
• 2. If the score is zero at any point, it means that the subarray from the start to the current index has an equal number of 1s and 0s.
• 3. Use a hash map to store the first occurrence of each score, and calculate the length of the subarray whenever the score is repeated.
Goal: The constraints are designed to ensure the solution can handle large inputs efficiently.
Steps:
• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.
Assumptions:
• The input array nums contains only 0s and 1s.
• Input: nums = [1, 0, 1, 0]
• Explanation: The entire array is a contiguous subarray with an equal number of 0s and 1s, so the answer is 4.
• Input: nums = [1, 1, 0, 0, 1, 0]
• Explanation: The longest contiguous subarray with an equal number of 0s and 1s is the entire array itself, so the answer is 6.
Approach: The approach involves using a score to track the difference between the counts of 1s and 0s in the array, and using a hash map to efficiently calculate the longest subarray with an equal number of 0s and 1s.
Observations:
• This problem can be solved using a technique based on prefix sums or difference arrays.
• By treating 1 as +1 and 0 as -1, we can use a cumulative sum to track the difference.
Steps:
• 1. Initialize a score variable to 0 and a hash map to store the first occurrence of each score.
• 2. Traverse through the array. For each element, update the score by adding 1 for a 1 or subtracting 1 for a 0.
• 3. If the score is 0, update the maximum subarray length as the current index + 1.
• 4. If the score is already in the hash map, calculate the length of the subarray from the first occurrence of the score to the current index and update the maximum length.
• 5. Return the maximum length found.
Empty Inputs:
• The solution should handle the edge case of an empty array.
Large Inputs:
• The solution should efficiently handle large arrays with a length up to 10^5.
Special Values:
• If the array contains only 0s or only 1s, the result should be 0 since no subarray with an equal number of 0s and 1s exists.
Constraints:
• The solution must handle arrays of length up to 10^5 in O(n) time complexity.
intfindMaxLength(vector<int>& nums) {
int n = nums.size();
int score =0, res =0;
map<int, int> mp;
for(int i =0; i < n; i++) {
score += nums[i]?1:-1;
if(score ==0) res = i +1;
else {
if(mp.count(score))
res = max(res, i - mp[score]);
if(!mp.count(score)) mp[score] = i;
}
}
return res;
}
1 : Function Definition
intfindMaxLength(vector<int>& nums) {
Defines the function `findMaxLength` that takes a vector `nums` of 1s and 0s, and returns the maximum length of a contiguous subarray where the number of 1s equals the number of 0s.
2 : Variable Initialization
int n = nums.size();
Initializes the variable `n` to store the size of the input array `nums`.
3 : Variable Initialization
int score =0, res =0;
Initializes two variables: `score` to track the current balance of 1s and 0s, and `res` to store the maximum length of the valid subarray found so far.
4 : Hash Map Initialization
map<int, int> mp;
Initializes a hash map `mp` that will store the first occurrence of each balance (`score`). This helps in finding the longest subarray with a sum of zero.
5 : Main Loop
for(int i =0; i < n; i++) {
Starts a loop to iterate through the array `nums`, updating the `score` and checking for the longest valid subarray.
6 : Balance Calculation
score += nums[i]?1:-1;
Updates the `score` by adding 1 if `nums[i]` is 1, or subtracting 1 if it is 0. This represents the balance of 1s and 0s.
7 : Check for Zero Balance
if(score ==0) res = i +1;
Checks if the `score` is zero, which means the subarray from the beginning to the current index has an equal number of 1s and 0s. If so, it updates `res` to be the length of this subarray.
8 : Handle Non-Zero Balance
else {
If `score` is not zero, it checks the hash map `mp` to determine the longest valid subarray.
9 : Check Map for Existing Balance
if(mp.count(score))
Checks if the `score` has been encountered before in the hash map `mp`. If it has, it means there exists a subarray that sums to zero between the previous occurrence of this balance and the current index.
10 : Update Result
res = max(res, i - mp[score]);
Updates `res` to the maximum length of the subarray found so far. This is done by comparing the current length (`i - mp[score]`) with the previous maximum length stored in `res`.
11 : Insert Score into Map
if(!mp.count(score)) mp[score] = i;
If the `score` has not been encountered before, it is added to the hash map `mp` with its index `i` as the value.
12 : Return Result
return res;
Returns the maximum length of a subarray with an equal number of 1s and 0s.
Best Case: O(n), where n is the length of the array.
Average Case: O(n)
Worst Case: O(n)
Description: In all cases, the time complexity is O(n) since we traverse the array once.
Best Case: O(1), if the score repeats immediately.
Worst Case: O(n), where n is the number of distinct scores encountered.
Description: The space complexity is O(n) due to the hash map storing the first occurrence of each score.
