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.

Description Solution Video 13:12

525. Contiguous Array

Medium52.2% acceptance16 companies

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.

Asked at 16 companies

Cisco Akamai Motive Amazon Meta Bloomberg Oracle

TCS

Infosys Adobe Walmart Labs Morgan Stanley

+4 more

Google Microsoft Tiktok Accenture

Topics

13:12

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

525. Contiguous Array

Asked at 16 companies

Topics

Similar problems