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.
Algorithm:
1. Replace all the 0's with -1, this will help us to find out the maximum length subarray with sum = 0.
2. Declare a HashMap, this will help us to find the subarray with sum=0 and start index is not 0.
3. Declare three variables sum, maxLength and endIndex. Initialize endIndex with -1 to handle cases where all 1's or 0's. endIndex=-1 means there is no such subarray.
4. Now we will start iterating, and update the sum.
5. If the sum is equal to 0, increment the maxLength and update endIndex.
6. We will check if the sum is present in the HashMap. If not present add the sum as key and value as index.
7. If the value is present, check if the difference of current index and previously stored value in hash (for the sum) is more than maxsize. If yes, update maxsize and endIndex.
8. Replace all the -1's with 0.
GIT URL: Java Solution of Leet Code's Contiguous Array problem
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.
Algorithm:
1. Replace all the 0's with -1, this will help us to find out the maximum length subarray with sum = 0.
2. Declare a HashMap, this will help us to find the subarray with sum=0 and start index is not 0.
3. Declare three variables sum, maxLength and endIndex. Initialize endIndex with -1 to handle cases where all 1's or 0's. endIndex=-1 means there is no such subarray.
4. Now we will start iterating, and update the sum.
5. If the sum is equal to 0, increment the maxLength and update endIndex.
6. We will check if the sum is present in the HashMap. If not present add the sum as key and value as index.
7. If the value is present, check if the difference of current index and previously stored value in hash (for the sum) is more than maxsize. If yes, update maxsize and endIndex.
8. Replace all the -1's with 0.
GIT URL: Java Solution of Leet Code's Contiguous Array problem
No comments:
Post a Comment