The O(n) Club: Contiguous Array: Find Your Zen Between 0s and 1s

The O(n) Club: Contiguous Array—Find Your Zen Between 0s and 1s

⚡ TL;DR

Want the longest streak where your array plays fair and tallies the exact same number of 0s and 1s, all in one go? Brute-force will have you looping until you wonder why you took up programming. Smart folks let a hash map and a running count do the work:

// Brute force classic: highly not recommended
for (int start = 0; start < n; start++) {
  for (int end = start; end < n; end++) {
    if (count0s == count1s) {
      // cry tears of inefficiency
    }
  }
}

🧠 How Devs Usually Mess This Up

People love writing code that checks every possible start and end pair—because who doesn’t want to relive O(n²) nightmares? Others try sliding windows, but that only works for subarrays with a fixed, predictable pattern—not here, because the moment you blink, the balance is off. Lastly, some folks get stuck on why 0 maps to -1. It’s not magic—it’s just the only way to actually measure balance with addition (math: still undefeated).

🔍 What’s Actually Going On

Imagine a group therapy session where every 0 gets a -1 sticker and every 1 gets a +1. As you walk through the binary array, you keep a running sum of their emotional baggage.

Every time the running sum hits a value it’s hit before, everything between those two moments has perfectly cancelled out their drama. By jotting down the first time you see every running sum with a hash map, you can find the subarray with the most peaceful balance (and longest length) in a single pass.

🛠️ PseudoCode

• Create a map to store: runningSum → firstIndex. Set map[0] = -1, so you can spot complete balance from the very start.
• runningSum = 0, maxLen = 0 (like every reliable hero’s beginning stats).
• For each index i in nums:
  • runningSum += (nums[i] == 0 ? -1 : 1);
  • If map already has runningSum:
    • maxLen = max(maxLen, i – map.get(runningSum)); // found a balance streak
  • Else: map.put(runningSum, i); // first sighting of this sum
• Return maxLen at the end—awards for most balanced drama.

💻 The Code

import java.util.HashMap;
 public class ContiguousArray {
    public int findMaxLength(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1); // Let the games begin, balanced from the start
        int runningSum = 0;
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            runningSum += (nums[i] == 0) ? -1 : 1;
            if (map.containsKey(runningSum)) {
                maxLen = Math.max(maxLen, i - map.get(runningSum));
            } else {
                map.put(runningSum, i);
            }
        }
        return maxLen;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Feed it all 0s or all 1s? You’ll just get 0—no cosmic balance here.
• If you forget that 0 → -1 mapping, your prefix sum will throw a tantrum (and your output will cry bugs).
• Don’t try to shoehorn sliding windows into this—save your window for actual panes of glass.
• Time/space: O(n). That’s efficient, and your interviewer might actually smile.

🧠 Interviewer Brain-Tattoo

Whenever you see the words ‘equal number of X and Y in a subarray’, just ask yourself: ‘Can I bother a hash map with my running sum one more time?’ Spoiler: Yes.