How do you solve Contiguous Array on LeetCode?

Contiguous Array (LeetCode #525) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Transforming the problem by treating 0 as -1 allows us to use cumulative sums effectively.

What is the brute force solution for Contiguous Array?

The brute force approach for Contiguous Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible subarray to see if it has an equal number of 0s and 1s. This is straightforward but inefficient because it examines all combinations. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Contiguous Array?

Contiguous Array uses the following concepts: Array, Hash Table, Prefix Sum. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Contiguous Array?

Always consider edge cases, like arrays with only 0s or only 1s. Explain your thought process clearly; it helps the interviewer understand your approach. Practice explaining the difference between brute force and optimal solutions.

What are common mistakes when solving Contiguous Array?

Not initializing the hash map correctly, which can lead to incorrect results. Overlooking the transformation of 0s to -1s, which is crucial for the optimal solution.

#525

Contiguous Array

Medium

ArrayHash TablePrefix SumHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach uses a hash map to track the cumulative count of 0s and 1s. By treating 0 as -1, we can find subarrays with equal counts by checking for the same cumulative sum at different indices.

⚙️

Algorithm

6 steps

1Step 1: Initialize a hash map to store the first occurrence of each cumulative sum.
2Step 2: Initialize variables for cumulative sum and maximum length.
3Step 3: Iterate through the array, updating the cumulative sum (increment for 1, decrement for 0).
4Step 4: If the cumulative sum has been seen before, calculate the length of the subarray and update the maximum length if it's longer.
5Step 5: If the cumulative sum hasn't been seen, store its index in the hash map.
6Step 6: Return the maximum length found.

solution.py13 lines

1# Full working Python code
2
3def findMaxLength(nums):
4    count_map = {0: -1}
5    max_length = 0
6    count = 0
7    for i, num in enumerate(nums):
8        count += 1 if num == 1 else -1
9        if count in count_map:
10            max_length = max(max_length, i - count_map[count])
11        else:
12            count_map[count] = i
13    return max_length

ℹ

Complexity note: The time complexity is O(n) because we traverse the array once. The space complexity is O(n) due to the hash map storing cumulative sums.

1Transforming the problem by treating 0 as -1 allows us to use cumulative sums effectively.
2Using a hash map to store indices of cumulative sums helps in quickly finding the lengths of subarrays.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.