Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Contiguous Array

Try it yourself
MediumProblemExternal link

Description

You get a binary array nums: every value is 0 or 1.

Return the length of the longest contiguous subarray that has the same number of 0s as 1s. If there is none, return 0.

Examples

Example 1

Input: nums = [0, 1]

Output: 2

Explanation: The whole array has one 0 and one 1.

Example 2

Input: nums = [0, 1, 0]

Output: 2

Explanation: [0, 1] and [1, 0] both balance; no subarray of length 3 can, since 3 is odd.

Example 3

Input: nums = [0, 1, 1, 1, 1, 1, 0, 0, 0]

Output: 6

Explanation: [1, 1, 1, 0, 0, 0], from index 3 to index 8, has three of each. No longer subarray balances.

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • nums[i] is either 0 or 1.

Editorial

Brute Force

Intuition

Try every start. From each one, extend to the right one value at a time, keeping the count of 1s minus 0s; whenever it's 0, the stretch balances, so remember its length if it's the longest yet.

Step-by-Step Explanation

For nums = [0, 1, 1, 1, 1, 1, 0, 0, 0]:

  1. The code tries every start in turn. Here is start 3, the one the answer comes from. Extend it one value at a time and count 1s minus 0s.
  2. Add nums[3] = 1: 1s minus 0s is now 1.
  3. Add nums[4] = 1: 1s minus 0s is now 2.
  4. Add nums[5] = 1: 1s minus 0s is now 3.
  5. Add nums[6] = 0: 1s minus 0s is now 2.
  6. Add nums[7] = 0: 1s minus 0s is now 1.
  7. Add nums[8] = 0: 1s minus 0s is now 0, so nums[3..8] balances, 6 values.
  8. The longest balanced stretch from start 3 has 6 values. The other starts do the same walk, which is what makes this O(n²).

Extend One Start — The shaded cells are the stretch so far; green marks an end where it balances.

Algorithm

  1. For each start s:
    • set diff to 0;
    • for each end e from s: add +1 for a 1 and −1 for a 0; if diff is 0, nums[s..e] balances.
  2. Return the longest balanced length found.

Code

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size(), best = 0;
        for (int s = 0; s < n; s++) {
            int diff = 0;                       // 1s minus 0s in nums[s..e]
            for (int e = s; e < n; e++) {
                diff += nums[e] == 1 ? 1 : -1;
                if (diff == 0) best = max(best, e - s + 1);
            }
        }
        return best;
    }
};

class Solution:
    def findMaxLength(self, nums: list[int]) -> int:
        n, best = len(nums), 0
        for s in range(n):
            diff = 0                            # 1s minus 0s in nums[s..e]
            for e in range(s, n):
                diff += 1 if nums[e] == 1 else -1
                if diff == 0 and e - s + 1 > best:
                    best = e - s + 1
        return best

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length, best = 0;
        for (int s = 0; s < n; s++) {
            int diff = 0;                       // 1s minus 0s in nums[s..e]
            for (int e = s; e < n; e++) {
                diff += nums[e] == 1 ? 1 : -1;
                if (diff == 0) best = Math.max(best, e - s + 1);
            }
        }
        return best;
    }
}

var findMaxLength = function(nums) {
    const n = nums.length;
    let best = 0;
    for (let s = 0; s < n; s++) {
        let diff = 0;                           // 1s minus 0s in nums[s..e]
        for (let e = s; e < n; e++) {
            diff += nums[e] === 1 ? 1 : -1;
            if (diff === 0) best = Math.max(best, e - s + 1);
        }
    }
    return best;
};

Complexity Analysis

Time Complexity: O(n²)

Every start extends to the end.

Space Complexity: O(1)

Why This Approach Is Not Efficient

With 10^5 values that's about 5 · 10^9 steps (over the time limit in cpp and Python and javascript).

Look at what diff really is: count each 1 as +1 and each 0 as −1, and a stretch balances exactly when its values add up to 0. That's a subarray-sum question, and those are answered with running totals.

Optimal Approach - Running Total and First Index

Intuition

Keep one running total over the whole array, +1 for each 1 and −1 for each 0. The stretch between two points adds up to the difference of the totals there, so it balances exactly when the two totals are equal. For the longest stretch ending at i, you want the earliest earlier point with the same total.

So keep a hash map from each total to the first index where it appeared, and never overwrite it. Start it with total 0 at index −1, the point before any value, so a stretch that starts at index 0 is found too.

Step-by-Step Explanation

For nums = [0, 1, 1, 1, 1, 1, 0, 0, 0]:

  1. Count each 1 as +1 and each 0 as −1. The map holds the first index where each running total appeared, and starts with total 0 at index −1, before any value.
  2. nums[0] is 0, so the total falls to −1. Total −1 is new, so the map records index 0 for it.
  3. nums[1] is 1, so the total rises to 0. Total 0 first appeared at index −1, so nums[0..1] balances, with 2 values, the longest so far.
  4. nums[2] is 1, so the total rises to 1. Total 1 is new, so the map records index 2 for it.
  5. nums[3] is 1, so the total rises to 2. Total 2 is new, so the map records index 3 for it.
  6. nums[4] is 1, so the total rises to 3. Total 3 is new, so the map records index 4 for it.
  7. nums[5] is 1, so the total rises to 4. Total 4 is new, so the map records index 5 for it.
  8. nums[6] is 0, so the total falls to 3. Total 3 first appeared at index 4, so nums[5..6] balances, with 2 values.
  9. nums[7] is 0, so the total falls to 2. Total 2 first appeared at index 3, so nums[4..7] balances, with 4 values, the longest so far.
  10. nums[8] is 0, so the total falls to 1. Total 1 first appeared at index 2, so nums[3..8] balances, with 6 values, the longest so far.
  11. The answer is 6, from one pass and one lookup per value.

Same Total Twice Means Balanced — Top: nums and the running total after each value. Bottom: the first index of each total, with the lookup highlighted.

Algorithm

  1. first = {0: -1}, total = 0, best = 0.
  2. For each index i: add +1 for a 1 and −1 for a 0 to total.
    • If total is in first, nums[first[total] + 1 .. i] balances: update best with i − first[total].
    • Otherwise record first[total] = i.
  3. Return best.

The totals stay between −n and n, so Java and C++ can use an array of 2n + 1 slots instead of a hash map, as the code below does.

Code

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> first(2 * n + 1, -2);       // total t lives at index t + n; -2 means not seen yet
        first[n] = -1;                          // total 0, before any value
        int total = 0, best = 0;
        for (int i = 0; i < n; i++) {
            total += nums[i] == 1 ? 1 : -1;     // a 0 counts as -1, so equal 0s and 1s add up to 0
            if (first[total + n] != -2) best = max(best, i - first[total + n]);
            else first[total + n] = i;          // keep the first: the earliest start is the longest
        }
        return best;
    }
};

class Solution:
    def findMaxLength(self, nums: list[int]) -> int:
        first = {0: -1}                         # running total -> the first index that reached it
        total = best = 0
        for i, x in enumerate(nums):
            total += 1 if x == 1 else -1        # a 0 counts as -1, so equal 0s and 1s add up to 0
            if total in first:
                best = max(best, i - first[total])
            else:
                first[total] = i                # keep the first: the earliest start is the longest
        return best

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int[] first = new int[2 * n + 1];       // total t lives at index t + n; -2 means not seen yet
        Arrays.fill(first, -2);
        first[n] = -1;                          // total 0, before any value
        int total = 0, best = 0;
        for (int i = 0; i < n; i++) {
            total += nums[i] == 1 ? 1 : -1;     // a 0 counts as -1, so equal 0s and 1s add up to 0
            if (first[total + n] != -2) best = Math.max(best, i - first[total + n]);
            else first[total + n] = i;          // keep the first: the earliest start is the longest
        }
        return best;
    }
}

var findMaxLength = function(nums) {
    const first = new Map([[0, -1]]);           // running total -> the first index that reached it
    let total = 0, best = 0;
    for (let i = 0; i < nums.length; i++) {
        total += nums[i] === 1 ? 1 : -1;        // a 0 counts as -1, so equal 0s and 1s add up to 0
        if (first.has(total)) best = Math.max(best, i - first.get(total));
        else first.set(total, i);               // keep the first: the earliest start is the longest
    }
    return best;
};

Complexity Analysis

Time Complexity: O(n)

One pass, one lookup per value.

Space Complexity: O(n)

Up to 2n + 1 different totals.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Starting with an empty map. first = {}

On nums = [0, 0, 1, 1], it returns 2; the answer is 4. A balanced stretch that starts at index 0 needs a start before any value, with running total 0. Without {0: -1} in the map nothing marks that start, so the stretch is missed: on [0, 0, 1, 1] the whole array balances, yet it finds only [0, 1].

Overwriting the first index. first[total] = i # on every step

On nums = [1, 0, 1, 0, 1, 1, 1], it returns 2; the answer is 4. For the longest stretch you want the earliest start, so the map must keep the first index where each total appeared. Overwriting it with every later index measures from the latest one instead.

Pairing up all the 0s and 1s. return 2 * min(ones, len(nums) - ones)

On nums = [1, 1, 0, 0, 0, 0, 1], it returns 6; the answer is 4. The 0s and 1s you'd pair up aren't necessarily next to each other. [1, 1, 0, 0, 0, 0, 1] has three 1s, so twice the smaller count is 6, but no stretch longer than 4 balances.

Adding the values as they are. total += x

On nums = [0, 1, 0, 1], it returns 1; the answer is 4. Adding the values as they are makes the running total count the 1s only, so two equal totals mean a stretch with no 1s at all. Count each 0 as -1: then equal totals mean as many 0s as 1s.

Where This Pattern Is Taught

This problem practises the longest subarray with a given sum, after turning 0s into −1s. It's taught in Prefix Sums with a Hash Map.