LeetCode 525: Contiguous Array Solution in Python – A Step-by-Step Guide

Imagine you’re flipping through a binary array—like [0, 1, 0, 1, 0]—and your mission is to find the longest stretch where the number of 0s equals the number of 1s, like [0, 1, 0, 1] with two of each. That’s the captivating challenge of LeetCode 525: Contiguous Array, a medium-level problem that’s a fantastic way to practice array techniques in Python. We’ll explore two solutions: the Best Solution, a prefix sum with hash map approach that’s efficient and clever, and an Alternative Solution, a brute-force subarray check that’s simple but slower. With detailed examples, clear code, and a friendly tone—especially for the hash map trick—this guide will help you balance that array, whether you’re new to coding or leveling up. Let’s dive into the 0s and 1s and start counting!

What Is LeetCode 525: Contiguous Array?

In LeetCode 525: Contiguous Array, you’re given a binary array nums containing only 0s and 1s, and your task is to find the length of the longest contiguous subarray where the count of 0s equals the count of 1s. For example, with nums = [0, 1], the entire array (length 2) has one 0 and one 1, so return 2. This problem tests prefix sums and balance tracking, related to LeetCode 560: Subarray Sum Equals K.

Problem Statement

Input: List of integers nums (0s and 1s only).
Output: Integer—length of longest contiguous subarray with equal 0s and 1s.
Rules: Subarray must be continuous; maximize length.

Constraints

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

Examples

Input: [0,1]

Output: 2
[0, 1] has 1 zero, 1 one.

Input: [0,1,0]

Output: 2
[0, 1] (length 2) is longest with equal counts.

Input: [0,0,1,1,0,1]

Output: 4
[0, 1, 1, 0] has 2 zeros, 2 ones.

Understanding the Problem: Balancing 0s and 1s

To solve LeetCode 525: Contiguous Array in Python, we need to find the longest continuous subarray where the number of 0s matches the number of 1s. A naive approach might check every subarray, but with up to 10⁵ elements, that’s inefficient. We’ll explore:

Best Solution (Prefix Sum with Hash Map): O(n) time, O(n) space—fast and smart.
Alternative Solution (Brute-Force Subarray Check): O(n²) time, O(1) space—simple but slow.

Let’s dive into the prefix sum solution with a friendly breakdown!

Best Solution: Prefix Sum with Hash Map

Why Prefix Sum Wins

The prefix sum with hash map is the best for LeetCode 525 because it transforms the problem into finding subarrays with a net balance of zero by treating 0s as -1 and 1s as +1, solving it in O(n) time and O(n) space. It’s like tracking a running score and spotting balanced segments!

How It Works

Think of this as a balance-tracking adventure:

Step 1: Transform 0s to -1s:

Replace 0s with -1s, so sum = #1s - #0s.
Equal 0s and 1s means sum = 0.

Step 2: Prefix Sums:

prefix[i] = sum from 0 to i.
If prefix[j] - prefix[i-1] = 0, then prefix[j] = prefix[i-1], and subarray i to j is balanced.

Step 3: Hash Map:

Store prefix sums with indices; if a sum repeats, compute length.

Step 4: Track Max Length:

Update max length when balance found.

Why It Works:

Same prefix sum means subarray sum = 0.
Hash map finds repeats efficiently.

It’s like a balance-spotting wizard!

Step-by-Step Example

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

Init: sum_map = {0: -1}, curr_sum = 0, max_len = 0.
Step 1: Transform and iterate:

i=0: 0→-1, curr_sum = -1, sum_map = {0: -1, -1: 0}.
i=1: 1, curr_sum = -1 + 1 = 0, sum_map[0] = -1, length = 1-(-1) = 2, max_len = 2.
i=2: 0→-1, curr_sum = 0 - 1 = -1, sum_map[-1] = 0, length = 2-0 = 2, max_len = 2.
i=3: 1, curr_sum = -1 + 1 = 0, sum_map[0] = -1, length = 3-(-1) = 4, max_len = 4.

Result: 4 ([0, 1, 0, 1]).

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        # Step 1: Initialize hash map and variables
        sum_map = {0: -1}  # Key: prefix sum, Value: earliest index
        curr_sum = 0
        max_len = 0

        # Step 2: Iterate through array
        for i in range(len(nums)):
            # Transform 0 to -1, 1 stays 1
            curr_sum += 1 if nums[i] == 1 else -1

            # Step 3: Check if sum seen before
            if curr_sum in sum_map:
                max_len = max(max_len, i - sum_map[curr_sum])
            else:
                sum_map[curr_sum] = i

        # Step 4: Return max length
        return max_len

Line 4: Map starts with 0 at -1 (empty sum).
Lines 5-6: Track current sum and max length.
Lines 9-10: Add 1 for 1, -1 for 0 to sum.
Lines 13-16: If sum repeats, compute length; else store index.
Line 19: Return longest balanced subarray.
Time Complexity: O(n)—single pass.
Space Complexity: O(n)—hash map size.

It’s like a balance-tracking genius!

Alternative Solution: Brute-Force Subarray Check

Why an Alternative Approach?

The brute-force solution checks every possible contiguous subarray, counting 0s and 1s to find the longest balanced one. It’s O(n²) time and O(1) space—intuitive but inefficient for large arrays. Great for grasping the basics!

How It Works

Picture this as a subarray sweep:

Step 1: For each start index i, check subarrays ending at j.
Step 2: Count 0s and 1s; if equal, update max length.
Step 3: Return max length found.

It’s like a manual balance checker!

Step-by-Step Example

Example: nums = [0, 1, 0]

Step 1: Check subarrays:

i=0: [0], [0,1], [0,1,0].

[0]: 1 zero, 0 ones.
[0,1]: 1 zero, 1 one, length = 2.
[0,1,0]: 2 zeros, 1 one.

i=1: [1], [1,0].

[1]: 0 zeros, 1 one.
[1,0]: 1 zero, 1 one, length = 2.

Step 2: Max length = 2.
Result: 2.

Code for Brute-Force Approach

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = 0

        # Step 1: Check all subarrays
        for i in range(n):
            zeros = 0
            ones = 0
            for j in range(i, n):
                if nums[j] == 0:
                    zeros += 1
                else:
                    ones += 1
                if zeros == ones:
                    max_len = max(max_len, j - i + 1)

        # Step 2: Return max length
        return max_len

Lines 6-15: Nested loops count 0s and 1s, update max length if balanced.
Line 18: Return result.
Time Complexity: O(n²)—all subarrays.
Space Complexity: O(1)—few variables.

It’s a slow balance sweeper!

Comparing the Two Solutions

Prefix Sum (Best):

Pros: O(n), O(n), efficient.
Cons: Hash map logic.

Brute-Force (Alternative):

Pros: O(n²), O(1), simple.
Cons: Too slow for large arrays.

Prefix sum wins for speed!

Additional Examples and Edge Cases

** [0]: 0 (no length ≥ 2).
** [1, 1]: 0 (no zeros).
** [0, 0, 1, 1]: 4.

Prefix sum handles them all!

Complexity Recap

Prefix Sum: Time O(n), Space O(n).
Brute-Force: Time O(n²), Space O(1).

Prefix sum’s the efficiency champ!

Key Takeaways

Prefix Sum: Balance tracking—learn at Python Basics!
Brute Force: Simple but costly.
Arrays: 0s and 1s are fun.
Python: Hash maps rule!

Final Thoughts: Balance That Array!

LeetCode 525: Contiguous Array in Python is a clever array challenge. Prefix sum with hash map is your fast track, while brute force shows the basics. Want more? Try LeetCode 560: Subarray Sum Equals K or LeetCode 974: Subarray Sums Divisible by K. Ready to balance? Head to Solve LeetCode 525 on LeetCode and find that equal stretch today!