Sponsored
Sponsored
The idea is to transform the array by converting 0s to -1s, which allows us to restate the problem as finding the longest contiguous subarray with a sum of 0. We can use a hash map to store the first occurrence of each prefix sum.
Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(n) for the hash map storage.
1var findMaxLength = function(nums) {
2 let countMap = {0: -1};
3 let maxLength = 0, count = 0;
4 for (let i = 0; i < nums.length; i++) {
5 count += nums[i] === 1 ? 1 : -1;
6 if (count in countMap) {
7 maxLength = Math.max(maxLength, i - countMap[count]);
8 } else {
9 countMap[count] = i;
10 }
11 }
12 return maxLength;
13};
14This JavaScript solution utilizes an object to store the first occurrences of various sums (count values), treating 0s as -1s. Loop through the array to calculate the maximum length of any balanced subarray found with these indices.
This simple approach checks every possible subarray and calculates its sum, verifying if it has an equal number of 0s and 1s. This method, while simple, serves as an exercise in understanding the problem better prior to using an optimized solution.
Time Complexity: O(n^2)
Space Complexity: O(1), as we do not use extra space other than primitive variables.
1publicEmploying nested loops, this Java solution checks all possible pairs of start and end indices within the array, verifying when counts of 0s and 1s match, and computing the maximum observed length.