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.
1import java.util.HashMap;
2
3public class Solution {
4 public int findMaxLength(int[] nums) {
5 HashMap<Integer, Integer> map = new HashMap<>();
6 map.put(0, -1);
7 int maxLength = 0, count = 0;
8 for (int i = 0; i < nums.length; i++) {
9 count += nums[i] == 1 ? 1 : -1;
10 if (map.containsKey(count)) {
11 maxLength = Math.max(maxLength, i - map.get(count));
12 } else {
13 map.put(count, i);
14 }
15 }
16 return maxLength;
17 }
18}
19This Java solution uses a HashMap to track the first occurrence of each accumulated count of 1s and 0s (with 0s represented as -1). We're trying to find the largest index difference with the same prefix sum.
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.
1class
By running two loops, this Python solution checks each subarray for equality of 0 and 1 counts, updating the maximum length found throughout each complete run.