Largest subarray of 0's and 1's

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Find largest subarray with equal count of 0s and 1s.

See our study guide for structured GFG and LeetCode practice.

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?