Skip to main content
Talentd

Contiguous Array - Solution & Explanation

MediumArrayHash TablePrefix Sum18 min readAsked at: Amazon, Microsoft, Meta +13
Practice this problem

Problem Statement

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 <= 105
  • 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.

In this C solution, we allocate an array hashMap to store the first indices of various counts. We initialize the map to -2, and the theoretical zero balance to -1. As we iterate over the array, we update the count for either 0s or 1s. We check if this count has been seen before and update the maximum length accordingly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(n) for the hash map 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.

This brute-force method iterates over each possible starting point and ending point of a subarray, counting the number of 0s and 1s and checking their equality. This gives a straightforward, albeit inefficient solution.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1), as we do not use extra space other than primitive variables.

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix Sum with Hash Map

Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(n) for the hash map storage.

Brute Force Approach

Time Complexity: O(n^2)
Space Complexity: O(1), as we do not use extra space other than primitive variables.

Prefix Sum + Hash Table—

Detailed Complexity Analysis

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

Video Solution

Contiguous array | Leetcode #525 • Techdose • 65,981 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Contiguous Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find All Possible Stable Binary Arrays I

Next

Find All Possible Stable Binary Arrays II