525. Contiguous Array - Solution

Q: Is Contiguous Array easy or hard?

Contiguous Array is considered a medium difficulty problem on LeetCode. The challenge comes from recognizing that the problem can be transformed into a prefix sum equality problem rather than checking all subarrays directly.

Q: How to solve Contiguous Array in O(n)?

Use a prefix sum technique where 0 is treated as -1 and 1 as +1. Maintain a running sum while iterating through the array and store the first index of each sum in a hash map. When the same sum appears again, the subarray between the two indices has equal numbers of 0s and 1s. Update the maximum length accordingly.

Q: What is the best approach for Contiguous Array?

The best approach uses prefix sum with a hash map. Convert 0 to -1 and 1 to +1, then track the running sum while traversing the array. If the same sum appears at two indices, the elements between them contain equal numbers of 0s and 1s. This method runs in O(n) time with O(n) space.

Q: What data structure is used in Contiguous Array?

The optimal solution relies on a hash map to store the first occurrence of each prefix sum. This allows constant-time lookups to determine whether the same cumulative value has appeared before. The approach is combined with prefix sum computation over the array.

Q: What is the time complexity of Contiguous Array?

The optimal solution runs in O(n) time because the array is traversed once while performing constant-time hash map lookups. The brute force approach checks every subarray and takes O(n²) time. Space complexity for the optimal solution is O(n) due to storing prefix sums in the hash map.

Q: Contiguous Array Python or Java solution approach?

Both Python and Java implementations follow the same idea: maintain a running prefix sum and store its earliest index in a hash map or dictionary. During traversal, if the sum has appeared before, compute the distance between indices and update the maximum length. The algorithm runs in O(n) time.

Q: Is Contiguous Array asked at Google, Amazon, or Meta?

Contiguous Array is a common prefix sum and hash map interview problem and has appeared in interviews at large tech companies such as Amazon, Google, and Meta. It tests understanding of prefix sums, hash-based lookups, and recognizing patterns in cumulative differences.

The problem

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

Example 2:

Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Constraints:

1 <= nums.length <= 10⁵
nums[i] is either 0 or 1.

Approach overview

Problem Overview: Given a binary array, find the length of the longest contiguous subarray containing the same number of 0s and 1s. The key observation is that equal counts mean their difference becomes zero over a range.

Approach 1: Brute Force (O(n²) time, O(1) space)

The straightforward approach checks every possible subarray. Start from each index i, iterate forward to j, and keep counters for 0s and 1s. Whenever both counts become equal, update the maximum length. This requires two nested loops over the array and constant extra space. The method works for small inputs but becomes slow as the array grows because it evaluates roughly n² subarrays.

This approach is useful when explaining the problem during interviews. It shows that you understand the requirement: a valid subarray must contain equal numbers of the two values. However, it does not scale for large inputs.

Approach 2: Prefix Sum with Hash Map (O(n) time, O(n) space)

The optimal approach converts the problem into a prefix sum problem. Treat every 0 as -1 and every 1 as +1. If two positions have the same cumulative sum, the subarray between them must contain equal numbers of 0s and 1s because their net contribution cancels out.

Traverse the array once while maintaining a running sum. Store the first index where each sum appears in a hash table. When the same sum appears again, compute the subarray length using the stored index and update the maximum. Initialize the map with sum = 0 at index -1 so subarrays starting at index 0 are handled correctly.

This method performs constant-time hash lookups while iterating through the array, giving linear time complexity. It is the standard solution used in competitive programming and technical interviews because it efficiently tracks prefix differences and avoids redundant subarray checks.

Recommended for interviews: Start by explaining the brute force idea to show your reasoning process. Then move to the prefix sum with hash map optimization. Interviewers typically expect the O(n) solution because it demonstrates familiarity with prefix sum patterns and hash-based lookups for tracking previously seen states.

Approach 1: Prefix Sum with Hash Map

The idea is to transform the array by converting 0s to -1s, which allows us to restate the problem as finding the longest contiguous subarray with a sum of 0. We can use a hash map to store the first occurrence of each prefix sum.

Python

class Solution:
    def findMaxLength(self, nums):
        count_map = {0: -1}
        max_length = count = 0
        for i, num in enumerate(nums):
            count += 1 if num == 1 else -1
            if count in count_map:
                max_length = max(max_length, i - count_map[count])
            else:
                count_map[count] = i
        return max_length

Java

import java.util.HashMap;

public class Solution {
    public int findMaxLength(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int maxLength = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i] == 1 ? 1 : -1;
            if (map.containsKey(count)) {
                maxLength = Math.max(maxLength, i - map.get(count));
            } else {
                map.put(count, i);
            }
        }
        return maxLength;
    }
}

C++

#include <unordered_map>
#include <vector>

int findMaxLength(std::vector<int>& nums) {
    std::unordered_map<int, int> countMap;
    countMap[0] = -1;
    int maxLength = 0, count = 0;
    for (int i = 0; i < nums.size(); i++) {
        count += (nums[i] == 1 ? 1 : -1);
        if (countMap.find(count) != countMap.end()) {
            maxLength = std::max(maxLength, i - countMap[count]);
        } else {
            countMap[count] = i;
        }
    }
    return maxLength;
}

JavaScript

var findMaxLength = function(nums) {
    let countMap = {0: -1};
    let maxLength = 0, count = 0;
    for (let i = 0; i < nums.length; i++) {
        count += nums[i] === 1 ? 1 : -1;
        if (count in countMap) {
            maxLength = Math.max(maxLength, i - countMap[count]);
        } else {
            countMap[count] = i;
        }
    }
    return maxLength;
};

#include <stdio.h>
#include <stdlib.h>

int findMaxLength(int* nums, int numsSize) {
    int maxLength = 0;
    int count = 0;
    int *hashMap = (int *)malloc(sizeof(int) * (2 * numsSize + 1));
    for (int i = 0; i < 2 * numsSize + 1; i++) hashMap[i] = -2;
    hashMap[numsSize] = -1;  // offset for 0 balance

    for (int i = 0; i < numsSize; i++) {
        count += (nums[i] == 1 ? 1 : -1);
        if (hashMap[count + numsSize] >= -1) {
            maxLength = (maxLength > i - hashMap[count + numsSize]) ? maxLength : i - hashMap[count + numsSize];
        } else {
            hashMap[count + numsSize] = i;
        }
    }

    free(hashMap);
    return maxLength;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int FindMaxLength(int[] nums) {
        Dictionary<int, int> countMap = new Dictionary<int, int>{{0, -1}};
        int maxLength = 0, count = 0;
        for (int i = 0; i < nums.Length; i++) {
            count += nums[i] == 1 ? 1 : -1;
            if (countMap.ContainsKey(count)) {
                maxLength = Math.Max(maxLength, i - countMap[count]);
            } else {
                countMap[count] = i;
            }
        }
        return maxLength;
    }
}

This Python solution employs a dictionary to hold the first occurrence of each count value. We increment or decrement count based on the value, and check whether we have seen this balance previously to evaluate maximum subarray length.

Complexity

Time Complexity: O(n)
Space Complexity: O(n) due to dictionary storage.

Try this approach in the editor

Approach 2: Brute Force Approach

This simple approach checks every possible subarray and calculates its sum, verifying if it has an equal number of 0s and 1s. This method, while simple, serves as an exercise in understanding the problem better prior to using an optimized solution.

Python

class Solution:
    def findMaxLength(self, nums):
        maxLength = 0
        for start in range(len(nums)):
            count0 = count1 = 0
            for end in range(start, len(nums)):
                if nums[end] == 0:
                    count0 += 1
                else:
                    count1 += 1

                if count0 == count1:
                    maxLength = max(maxLength, end - start + 1)
        return maxLength

Java

public class Solution {
    public int findMaxLength(int[] nums) {
        int maxLength = 0;
        for (int start = 0; start < nums.length; start++) {
            int count0 = 0, count1 = 0;
            for (int end = start; end < nums.length; end++) {
                if (nums[end] == 0) count0++;
                else count1++;
                if (count0 == count1) {
                    maxLength = Math.max(maxLength, end - start + 1);
                }
            }
        }
        return maxLength;
    }
}

C++

#include <vector>

int findMaxLength(std::vector<int>& nums) {
    int maxLength = 0;
    for (int start = 0; start < nums.size(); start++) {
        int count0 = 0, count1 = 0;
        for (int end = start; end < nums.size(); end++) {
            nums[end] == 0 ? count0++ : count1++;
            if (count0 == count1) {
                maxLength = std::max(maxLength, end - start + 1);
            }
        }
    }
    return maxLength;
}

JavaScript

var findMaxLength = function(nums) {
    let maxLength = 0;
    for (let start = 0; start < nums.length; start++) {
        let count0 = 0, count1 = 0;
        for (let end = start; end < nums.length; end++) {
            nums[end] === 0 ? count0++ : count1++;
            if (count0 === count1) {
                maxLength = Math.max(maxLength, end - start + 1);
            }
        }
    }
    return maxLength;
};

#include <stdio.h>

int findMaxLength(int* nums, int numsSize) {
    int maxLength = 0;
    for (int start = 0; start < numsSize; start++) {
        int count0 = 0, count1 = 0;
        for (int end = start; end < numsSize; end++) {
            if (nums[end] == 0) count0++;
            else count1++;

            if (count0 == count1) {
                int length = end - start + 1;
                if (length > maxLength) {
                    maxLength = length;
                }
            }
        }
    }
    return maxLength;
}

public class Solution {
    public int FindMaxLength(int[] nums) {
        int maxLength = 0;
        for (int start = 0; start < nums.Length; start++) {
            int count0 = 0, count1 = 0;
            for (int end = start; end < nums.Length; end++) {
                if (nums[end] == 0) count0++;
                else count1++;
                if (count0 == count1) {
                    maxLength = Math.Max(maxLength, end - start + 1);
                }
            }
        }
        return maxLength;
    }
}

By running two loops, this Python solution checks each subarray for equality of 0 and 1 counts, updating the maximum length found throughout each complete run.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1), leveraging direct use of integers only.

Try this approach in the editor

Approach 3: Prefix Sum + Hash Table

According to the problem description, we can treat 0s in the array as -1. In this way, when encountering a 0, the prefix sum s will decrease by one, and when encountering a 1, the prefix sum s will increase by one. Therefore, suppose the prefix sum s is equal at indices j and i, where j < i, then the subarray from index j + 1 to i has an equal number of 0s and 1s.

We use a hash table to store all prefix sums and their first occurrence indices. Initially, we map the prefix sum of 0 to -1.

As we iterate through the array, we calculate the prefix sum s. If s is already in the hash table, then we have found a subarray with a sum of 0, and its length is i - d[s], where d[s] is the index where s first appeared in the hash table. If s is not in the hash table, we store s and its index i in the hash table.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.

TypeScript

function findMaxLength(nums: number[]): number {
    const d: Record<number, number> = { 0: -1 };
    let ans = 0;
    let s = 0;
    for (let i = 0; i < nums.length; ++i) {
        s += nums[i] ? 1 : -1;
        if (d.hasOwnProperty(s)) {
            ans = Math.max(ans, i - d[s]);
        } else {
            d[s] = i;
        }
    }
    return ans;
}

func findMaxLength(nums []int) int {
	d := map[int]int{0: -1}
	ans, s := 0, 0
	for i, x := range nums {
		if x == 0 {
			x = -1
		}
		s += x
		if j, ok := d[s]; ok {
			ans = max(ans, i-j)
		} else {
			d[s] = i
		}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Prefix Sum with Hash Map	Time Complexity: O(n) Space Complexity: O(n) due to dictionary storage.
Brute Force Approach	Time Complexity: O(n^2) Space Complexity: O(1), leveraging direct use of integers only.
Prefix Sum + Hash Table	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Subarray Scan	O(n²)	O(1)	Good for understanding the problem logic or when input size is very small
Prefix Sum with Hash Map	O(n)	O(n)	Best general solution; handles large arrays efficiently using prefix difference tracking

Frequently asked questions

Is Contiguous Array easy or hard?

Contiguous Array is considered a medium difficulty problem on LeetCode. The challenge comes from recognizing that the problem can be transformed into a prefix sum equality problem rather than checking all subarrays directly.

How to solve Contiguous Array in O(n)?

Use a prefix sum technique where 0 is treated as -1 and 1 as +1. Maintain a running sum while iterating through the array and store the first index of each sum in a hash map. When the same sum appears again, the subarray between the two indices has equal numbers of 0s and 1s. Update the maximum length accordingly.

What is the best approach for Contiguous Array?

The best approach uses prefix sum with a hash map. Convert 0 to -1 and 1 to +1, then track the running sum while traversing the array. If the same sum appears at two indices, the elements between them contain equal numbers of 0s and 1s. This method runs in O(n) time with O(n) space.

What data structure is used in Contiguous Array?

The optimal solution relies on a hash map to store the first occurrence of each prefix sum. This allows constant-time lookups to determine whether the same cumulative value has appeared before. The approach is combined with prefix sum computation over the array.

What is the time complexity of Contiguous Array?

The optimal solution runs in O(n) time because the array is traversed once while performing constant-time hash map lookups. The brute force approach checks every subarray and takes O(n²) time. Space complexity for the optimal solution is O(n) due to storing prefix sums in the hash map.

Contiguous Array Python or Java solution approach?

Both Python and Java implementations follow the same idea: maintain a running prefix sum and store its earliest index in a hash map or dictionary. During traversal, if the sum has appeared before, compute the distance between indices and update the maximum length. The algorithm runs in O(n) time.

Is Contiguous Array asked at Google, Amazon, or Meta?

Contiguous Array is a common prefix sum and hash map interview problem and has appeared in interviews at large tech companies such as Amazon, Google, and Meta. It tests understanding of prefix sums, hash-based lookups, and recognizing patterns in cumulative differences.

Contiguous Array solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum with Hash Map

Approach 2: Brute Force Approach

Approach 3: Prefix Sum + Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Contiguous Array solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum with Hash Map

Approach 2: Brute Force Approach

Approach 3: Prefix Sum + Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems