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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int findMaxLength(int* nums, int numsSize) {
5 int maxLength = 0;
6 int count = 0;
7 int *hashMap = (int *)malloc(sizeof(int) * (2 * numsSize + 1));
8 for (int i = 0; i < 2 * numsSize + 1; i++) hashMap[i] = -2;
9 hashMap[numsSize] = -1; // offset for 0 balance
10
11 for (int i = 0; i < numsSize; i++) {
12 count += (nums[i] == 1 ? 1 : -1);
13 if (hashMap[count + numsSize] >= -1) {
14 maxLength = (maxLength > i - hashMap[count + numsSize]) ? maxLength : i - hashMap[count + numsSize];
15 } else {
16 hashMap[count + numsSize] = i;
17 }
18 }
19
20 free(hashMap);
21 return maxLength;
22}
23In this C solution, we allocate an array hashMap to store the first indices of various counts. We initialize the map to -2, and the theoretical zero balance to -1. As we iterate over the array, we update the count for either 0s or 1s. We check if this count has been seen before and update the maximum length accordingly.
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.
1public class Solution {
public int FindMaxLength(int[] nums) {
int maxLength = 0;
for (int start = 0; start < nums.Length; start++) {
int count0 = 0, count1 = 0;
for (int end = start; end < nums.Length; end++) {
if (nums[end] == 0) count0++;
else count1++;
if (count0 == count1) {
maxLength = Math.Max(maxLength, end - start + 1);
}
}
}
return maxLength;
}
}
This C# brute force option methodically tests each range of elements possible in the array, adjusting the leading maximum possible length each period the balance (0s and 1s) occurs.