Contiguous Array

Contiguous Array

What is this problem about?

The Contiguous Array interview question gives you a binary array (containing only 0s and 1s). You need to find the maximum length of a contiguous subarray that contains an equal number of 0s and 1s.

Why is this asked in interviews?

Companies like Meta, Amazon, and Adobe use the Contiguous Array coding problem to test a candidate's ability to use the Prefix Sum technique creatively. It requires a mathematical transformation of the input to reveal a simpler sub-problem.

Algorithmic pattern used

This problem follows the Array, Hash Table, Prefix Sum interview pattern.

1. Treat all 0s as -1 and all 1s as +1.
2. Now the problem becomes: find the longest subarray whose sum is 0.
3. Calculate the running prefix sum. If the same sum appears at index i and index j, the subarray between them must have a sum of 0.
4. Use a Hash Map to store the first occurrence of each prefix sum. The difference between the current index and the stored index is a candidate for the maximum length.

Example explanation

Array: [0, 1, 0, 0, 1, 1] Transform: [-1, 1, -1, -1, 1, 1]

1. Sum=0: Index -1 (Initial state).
2. Sum=-1: Index 0. Map: {-1: 0, 0: -1}
3. Sum=0: Seen at -1. Length = 1 - (-1) = 2.
4. Sum=-1: Seen at 0. Length = 2 - 0 = 2.
5. Sum=-2: Index 3. Map: {-1: 0, 0: -1, -2: 3}
6. Sum=-1: Seen at 0. Length = 4 - 0 = 4.
7. Sum=0: Seen at -1. Length = 5 - (-1) = 6. Max length = 6.

Common mistakes candidates make

• Not initializing the Map: Forgetting to put {0: -1} in the map, which prevents finding subarrays that start from the very beginning of the original array.
• Updating indices: Storing the latest index of a sum instead of the earliest. To maximize length, you want the earliest possible start.
• Brute force: Checking every subarray (O(N^2)), which will time out for large arrays.

Interview preparation tip

The trick of "treating 0 as -1" is a classic pattern for balancing problems. Whenever you need to find "equal counts" of two items, mapping them to 1 and -1 and using prefix sums is often the most optimal path.