Largest subarray of 0's and 1's

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Find largest subarray with equal count of 0s and 1s. Replace 0 with -1, find max subarray with sum=0.

Algorithm

1Replace 0s with -1. Prefix sum approach: find max (j-i) where prefix[i] == prefix[j].
2HashMap stores first occurrence index of each prefix sum.

Common Pitfalls

•Same as LC 525. Transform then use prefix sum hashmap. Initialize map with {0: -1}.

Largest subarray of 0's and 1's.java

Java

// Approach: Replace 0s with -1s. Problem reduces to finding the longest subarray with sum 0 using prefix sum HashMap.
// Time: O(n) Space: O(n)
class Solution {
    public int maxLen(int[] arr) {
        int n = arr.length;
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            if (arr[i] == 0)
                arr[i] = -1;
        }

        int sum = 0;
        int max = 0;

        for (int i = 0; i < n; i++) {
            sum += arr[i];
            if (sum == 0) {
                max = i + 1;
                continue;
            }

            if (map.containsKey(sum))
                max = Math.max(max, i - map.get(sum));
            else
                map.put(sum, i);
        }

        return max;
    }
}

Was this solution helpful?