What is the time complexity of Contiguous Array?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Contiguous Array?

This problem uses Array, Hash Table, Prefix Sum. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Contiguous Array?

Insight 1: Instead of directly counting 0s and 1s in subarrays, we can transform the 0s into -1s. Then, the problem becomes finding the longest subarray whose sum is 0. Insight 2: We can use a hash table (or map) to store the prefix sum at each index. If we encounter the same prefix sum again at a later index, it means that the subarray between those two indices has a sum of 0.

Which companies ask LeetCode 525. Contiguous Array in interviews?

This problem is frequently asked at Morgan Stanley.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Contiguous Array - LeetCode 525 Solution

Contiguous Array - Complete Solution Guide

Contiguous Array is LeetCode problem 525, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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. Example 3: Input: nums = [0,1,1,1,1,1,0,0,0] Output: 6 Explanation: [1,1,1,0,0,0] is the longest contiguous subarray wit

Detailed Explanation

The problem asks us to find the maximum length of a contiguous subarray within a given binary array (an array containing only 0s and 1s) that has an equal number of 0s and 1s. For example, in the array [0, 1, 0, 1], the subarrays [0, 1] and [1, 0] each have an equal number of 0s and 1s, and their length is 2. The subarray [0, 1, 0, 1] also has equal 0s and 1s and has a length of 4. The goal is to find the *longest* such subarray. The input is an array `nums` of 0s and 1s, and the output is the maximum length of a contiguous subarray with an equal number of 0s and 1s.

Solution Approach

The solution uses a prefix sum approach combined with a hash table. We iterate through the array, maintaining a running 'count'. Each time we encounter a 1, we increment the count. Each time we encounter a 0, we decrement the count (treat it as -1). We store the first occurrence of each count value in a hash table, along with its index. When we encounter the same count value again at a later index, it means the subarray between the current index and the index stored in the hash table sums to 0 (equal number of 0s and 1s). We then update the maximum length accordingly.

Step-by-Step Algorithm

Step 1: Initialize a hash map `count_map` to store the first occurrence of each count, with an initial entry `{0: -1}`. This entry accounts for subarrays starting from the beginning of the array.
Step 2: Initialize `max_len` to 0 to store the maximum length found so far.
Step 3: Initialize `count` to 0 to store the running count.
Step 4: Iterate through the input array `nums` using a `for` loop and index `i`.
Step 5: For each element `num` in `nums`, update the `count`. If `num` is 1, increment `count`; otherwise (if `num` is 0), decrement `count`.
Step 6: Check if `count` is already present in the `count_map`.
Step 7: If `count` is in `count_map`, it means we have encountered this prefix sum before. Calculate the length of the subarray between the current index `i` and the index stored in `count_map[count]`. Update `max_len` with the maximum of the current `max_len` and the calculated length.
Step 8: If `count` is not in `count_map`, store the current `count` and its index `i` in the `count_map`.
Step 9: After iterating through the entire array, return `max_len`.

Key Insights

Insight 1: Instead of directly counting 0s and 1s in subarrays, we can transform the 0s into -1s. Then, the problem becomes finding the longest subarray whose sum is 0.
Insight 2: We can use a hash table (or map) to store the prefix sum at each index. If we encounter the same prefix sum again at a later index, it means that the subarray between those two indices has a sum of 0.
Insight 3: Initialize the hash map with {0: -1}. This is to handle the case where a subarray starting from index 0 has an equal number of 0s and 1s.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Prefix Sum.

Companies

Asked at: Morgan Stanley.

Contiguous Array | LeetCode 525

Medium

Array Hash Table Prefix Sum

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.HashMap;
import java.util.Map;

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

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 525: Contiguous Array - Detailed explanation and solution approaches.

Topics

Array Hash Table Prefix Sum

Companies

Morgan Stanley

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:525

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Initialize a hash map `count_map` to store the first occurrence of each count, with an initial entry `{0: -1}`. This entry accounts for subarrays starting from the beginning of the array.
2
Step 2: Initialize `max_len` to 0 to store the maximum length found so far.
3
Step 3: Initialize `count` to 0 to store the running count.
4
Step 4: Iterate through the input array `nums` using a `for` loop and index `i`.
5
Step 5: For each element `num` in `nums`, update the `count`. If `num` is 1, increment `count`; otherwise (if `num` is 0), decrement `count`.
6
Step 6: Check if `count` is already present in the `count_map`.
7
Step 7: If `count` is in `count_map`, it means we have encountered this prefix sum before. Calculate the length of the subarray between the current index `i` and the index stored in `count_map[count]`. Update `max_len` with the maximum of the current `max_len` and the calculated length.
8
Step 8: If `count` is not in `count_map`, store the current `count` and its index `i` in the `count_map`.
9
Step 9: After iterating through the entire array, return `max_len`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is O(n) because the algorithm iterates through the input array once. The space complexity is O(n) because, in the worst case, the hash table might need to store n different prefix sums, requiring space proportional to the input size. For example, the array `[0, 1, 0, 1, 0, 1, ...]` would generate unique prefix sums for each index, up to `n/2` then back down to `-n/2`.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Iterate through all possible subarrays and check if each subarray has an equal number of 0s and 1s. If it does, update the maximum length.

Time: O(n^2), where n is the length of the input array.Space: O(1)

Trade-offs: This approach is simple to understand but inefficient for large input arrays. The hash table approach is significantly faster. Avoid brute force unless n is very small.

✨

Key Insights

1Insight 1: Instead of directly counting 0s and 1s in subarrays, we can transform the 0s into -1s. Then, the problem becomes finding the longest subarray whose sum is 0.
2Insight 2: We can use a hash table (or map) to store the prefix sum at each index. If we encounter the same prefix sum again at a later index, it means that the subarray between those two indices has a sum of 0.
3Insight 3: Initialize the hash map with {0: -1}. This is to handle the case where a subarray starting from index 0 has an equal number of 0s and 1s.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: Empty input array or an array with only one element. The code works correctly as the loop won't execute if the array is empty and for single element the count will either be 1 or -1, which is not in count_map so the map is updated with {0: -1, count : index}. This doesn't affect the outcome, as max_len remains 0, which is the correct answer.
Edge case 2: An array with all 0s or all 1s. In this case, the count will either monotonically decrease or increase, respectively. No count will be repeated, and the `max_len` will remain 0, which is the correct answer since such arrays don't have any contiguous subarray with equal numbers of 0s and 1s.
Edge case 3: When the whole array has equal number of 0s and 1s, the correct length should be the size of input array. The initial {0: -1} handles this case properly because after going through the whole array the final 'count' will be 0, which exists in count_map already, and the length will be i - (-1), where i = nums.size() -1, therefore nums.size()

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to initialize the hash map with `{0: -1}`. This is crucial for handling cases where a subarray starting from index 0 has an equal number of 0s and 1s.

✗Common mistake 2: Not using the correct calculation for the length of the subarray. The length is `i - count_map[count]`, where `i` is the current index and `count_map[count]` is the first index where that `count` was encountered.

✗Common mistake 3: Confusing the roles of 0 and 1 and inadvertently incrementing the count for zeros and decrementing for ones

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Signal processing. This algorithm can be used to find patterns in binary signals where a balanced sequence is desired or significant.

🏦Real-world scenario 2: Data compression. In some data compression algorithms, identifying balanced sequences of bits can help optimize the compression process.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 13, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Contiguous Array"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?