Jobs

Interviews

Discussions

Contiguous Array

Medium

Morgan Stanley

0 views

Topics:

ArraysHash Table

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 with equal number of 0 and 1.

Constraints:

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

Try coding it in LeetCode

Contiguous Array

Medium

Morgan Stanley

0 views

Topics:

ArraysHash Table

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 with equal number of 0 and 1.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `nums`?
Can the input array `nums` be empty or null?
If there is no contiguous subarray with an equal number of 0s and 1s, what value should I return?
Are the values in the array guaranteed to be only 0 or 1, or could there be other integer values?
If there are multiple contiguous subarrays with the same maximum length and an equal number of 0s and 1s, is it sufficient to return the length of any one of them?

Brute Force Solution

Approach

To find the longest segment of an amount of numbers with an equal amount of 0s and 1s, the brute force way is to check every possible segment. This involves looking at all possible starting and ending points and then checking if the segment between them meets our condition.

Here's how the algorithm would work step-by-step:

Start by looking at the segment starting at the very first number and ending right after it.
Then, look at the segment starting at the first number and extending two numbers.
Keep extending the end of the segment, one number at a time, checking each time if the number of 0s and 1s are equal in that segment.
Once you've checked all segments starting from the first number, move to the second number and repeat the process.
Do this for every number in the series, as a potential starting point.
Each time you find a segment where the number of 0s and 1s are equal, remember the length of that segment.
In the end, compare the lengths of all the segments you found that met the condition, and pick the longest one.

Code Implementation

def find_maxLength_brute_force(numbers):
    maximum_length = 0

    for start_index in range(len(numbers)):
        for end_index in range(start_index, len(numbers)):
            # Consider all subarrays
            subarray = numbers[start_index:end_index+1]

            zeros_count = 0
            ones_count = 0

            for number in subarray:
                if number == 0:
                    zeros_count += 1
                else:
                    ones_count += 1

            # Check for equal 0s and 1s
            if zeros_count == ones_count:

                current_length = end_index - start_index + 1

                # Find the maximum length
                maximum_length = max(maximum_length, current_length)

    return maximum_length

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all possible subarrays within the given array of size n. For each starting index i (from 0 to n-1), it iterates through all possible ending indices j (from i+1 to n-1). For each subarray defined by i and j, it counts the number of 0s and 1s to check if they are equal. The outer loop runs n times, and the inner loop, on average, runs n/2 times. Therefore, the total number of operations is proportional to n * (n/2) which simplifies to O(n²).

Space Complexity

O(1) – The brute force approach iterates through all possible subarrays using nested loops, but it doesn't use any extra data structures that scale with the input size N (the number of elements in the input array). Only a few constant-size variables, such as the current segment's start and end indices, and the count of zeros and ones, are used. Therefore, the auxiliary space required remains constant regardless of the input array's size. The space complexity is O(1).

Optimal Solution

Approach

The problem asks us to find the longest part of the sequence where the number of 0s and 1s are equal. We can use a trick to keep track of the difference between the number of 0s and 1s we have seen so far, and use that to efficiently find matching segments.

Here's how the algorithm would work step-by-step:

Imagine you are walking along the sequence, keeping a score of the difference between the number of 1s and 0s.
Every time you see a 1, you add one to the score; every time you see a 0, you subtract one.
Keep track of the score you've encountered. If you find the same score twice, the portion of the sequence between those two occurrences has the same number of 0s and 1s.
The goal is to find the largest such portion between any two identical scores.
Use a special notebook to remember the first time you saw each score. If you see the same score again, you know there's a portion with an equal number of 0s and 1s.
Whenever you find a score you've seen before, calculate the length of that portion and update your answer with the largest length found so far.

Code Implementation

def find_max_length(nums):
    max_length = 0
    count_difference = 0
    # Store the first index seen for each count difference.
    count_index_map = {0: -1}

    for index, number in enumerate(nums):
        if number == 1:
            count_difference += 1
        else:
            count_difference -= 1

        # If we've seen this difference before,
        if count_difference in count_index_map:
            # It means there's an equal amount of 0s and 1s between the indices.
            max_length = max(max_length, index - count_index_map[count_difference])
        else:
            # Store the first index this difference was encountered.
            count_index_map[count_difference] = index

    return max_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n once. Inside the loop, each element is processed in constant time. The hash map operations (put and get) have an average time complexity of O(1). Therefore, the overall time complexity is driven by the single pass through the array, resulting in O(n) time complexity.

Space Complexity

O(N) – The primary auxiliary space usage comes from the "special notebook" mentioned in the problem description, which functions as a hash map (or dictionary). This hash map stores the first occurrence of each score (difference between 1s and 0s). In the worst case, the score could range from -N to N, requiring us to store up to N unique scores. Therefore, the space complexity is proportional to the input size N.

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there's no subarray.
Input array with only one element	Return 0 since a subarray with equal 0s and 1s requires at least two elements.
Array with all 0s	The prefix sum will decrease linearly; the solution must handle negative prefix sums correctly, returning 0 if no equal count subarray is found.
Array with all 1s	The prefix sum will increase linearly; the solution must return 0 if no equal count subarray is found.
Large input array causing potential integer overflow in prefix sum calculation	Use a data type that can accommodate larger prefix sum values, or handle overflow explicitly (though overflow is unlikely with a boolean input).
Array with a very long subarray of alternating 0s and 1s	Ensure the solution's time complexity is linear to avoid timeouts with large inputs.
No subarray with equal 0s and 1s exists	The solution should correctly return 0 in this case.
Input array contains non-binary values	The problem statement explicitly specifies a binary array, so this case isn't strictly necessary, but you may want to clarify assumptions about input validation with the interviewer.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `nums`?
Can the input array `nums` be empty or null?
If there is no contiguous subarray with an equal number of 0s and 1s, what value should I return?
Are the values in the array guaranteed to be only 0 or 1, or could there be other integer values?
If there are multiple contiguous subarrays with the same maximum length and an equal number of 0s and 1s, is it sufficient to return the length of any one of them?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the segment starting at the very first number and ending right after it.
Then, look at the segment starting at the first number and extending two numbers.
Keep extending the end of the segment, one number at a time, checking each time if the number of 0s and 1s are equal in that segment.
Once you've checked all segments starting from the first number, move to the second number and repeat the process.
Do this for every number in the series, as a potential starting point.
Each time you find a segment where the number of 0s and 1s are equal, remember the length of that segment.
In the end, compare the lengths of all the segments you found that met the condition, and pick the longest one.

Code Implementation

def find_maxLength_brute_force(numbers):
    maximum_length = 0

    for start_index in range(len(numbers)):
        for end_index in range(start_index, len(numbers)):
            # Consider all subarrays
            subarray = numbers[start_index:end_index+1]

            zeros_count = 0
            ones_count = 0

            for number in subarray:
                if number == 0:
                    zeros_count += 1
                else:
                    ones_count += 1

            # Check for equal 0s and 1s
            if zeros_count == ones_count:

                current_length = end_index - start_index + 1

                # Find the maximum length
                maximum_length = max(maximum_length, current_length)

    return maximum_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you are walking along the sequence, keeping a score of the difference between the number of 1s and 0s.
Every time you see a 1, you add one to the score; every time you see a 0, you subtract one.
Keep track of the score you've encountered. If you find the same score twice, the portion of the sequence between those two occurrences has the same number of 0s and 1s.
The goal is to find the largest such portion between any two identical scores.
Use a special notebook to remember the first time you saw each score. If you see the same score again, you know there's a portion with an equal number of 0s and 1s.
Whenever you find a score you've seen before, calculate the length of that portion and update your answer with the largest length found so far.

Code Implementation

def find_max_length(nums):
    max_length = 0
    count_difference = 0
    # Store the first index seen for each count difference.
    count_index_map = {0: -1}

    for index, number in enumerate(nums):
        if number == 1:
            count_difference += 1
        else:
            count_difference -= 1

        # If we've seen this difference before,
        if count_difference in count_index_map:
            # It means there's an equal amount of 0s and 1s between the indices.
            max_length = max(max_length, index - count_index_map[count_difference])
        else:
            # Store the first index this difference was encountered.
            count_index_map[count_difference] = index

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there's no subarray.
Input array with only one element	Return 0 since a subarray with equal 0s and 1s requires at least two elements.
Array with all 0s	The prefix sum will decrease linearly; the solution must handle negative prefix sums correctly, returning 0 if no equal count subarray is found.
Array with all 1s	The prefix sum will increase linearly; the solution must return 0 if no equal count subarray is found.
Large input array causing potential integer overflow in prefix sum calculation	Use a data type that can accommodate larger prefix sum values, or handle overflow explicitly (though overflow is unlikely with a boolean input).
Array with a very long subarray of alternating 0s and 1s	Ensure the solution's time complexity is linear to avoid timeouts with large inputs.
No subarray with equal 0s and 1s exists	The solution should correctly return 0 in this case.
Input array contains non-binary values	The problem statement explicitly specifies a binary array, so this case isn't strictly necessary, but you may want to clarify assumptions about input validation with the interviewer.