Jobs

Interviews

Discussions

Max Consecutive Ones III

Medium

Amazon

4 views

Topics:

ArraysSliding WindowsTwo Pointers

You are given a binary array nums (containing only 0s and 1s) and an integer k. Your task is to find the maximum number of consecutive 1s in the array if you are allowed to flip at most k 0s to 1s.

For example:

If nums = [1,1,1,0,0,0,1,1,1,1,0] and k = 2, the output should be 6 because you can flip two 0s to get [1,1,1,0,0,1,1,1,1,1,1], and the longest consecutive 1s subarray is [1,1,1,1,1,1] (length 6 after taking a sub-array).
If nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1] and k = 3, the output should be 10 because you can flip three 0s to get [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1], and the longest consecutive 1s subarray is [1,1,1,1,1,1,1,1,1,1] (length 10 after taking a sub-array).

Describe an efficient algorithm to solve this problem. What is the time and space complexity of your solution? Can you provide code for your solution? What are some edge cases to consider?

Max Consecutive Ones III

Medium

Amazon

4 views

Topics:

ArraysSliding WindowsTwo Pointers

For example:

If nums = [1,1,1,0,0,0,1,1,1,1,0] and k = 2, the output should be 6 because you can flip two 0s to get [1,1,1,0,0,1,1,1,1,1,1], and the longest consecutive 1s subarray is [1,1,1,1,1,1] (length 6 after taking a sub-array).
If nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1] and k = 3, the output should be 10 because you can flip three 0s to get [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1], and the longest consecutive 1s subarray is [1,1,1,1,1,1,1,1,1,1] (length 10 after taking a sub-array).

Describe an efficient algorithm to solve this problem. What is the time and space complexity of your solution? Can you provide code for your solution? What are some edge cases to consider?

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` and the maximum value of `k`?
Can the input array `nums` be empty or null?
If `k` is zero, and `nums` contains only zeros, what should the return value be?
Are the values in `nums` guaranteed to be only 0 or 1?
If there are multiple subarrays of the same maximum length after flipping at most `k` zeros, can I return the length of any of them?

Brute Force Solution

Approach

The brute force approach to finding the longest sequence of consecutive ones involves checking every possible sub-sequence within the given sequence. We will examine all possible starting positions and lengths. For each of these sub-sequences, we determine if we can achieve all ones by flipping at most a certain amount of zeros.

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

Consider every possible starting point in the sequence.
For each starting point, consider every possible length of the sub-sequence that begins there.
For each sub-sequence, count how many zeros are within it.
Check if the number of zeros within the sub-sequence is less than or equal to the allowed number of flips.
If the number of zeros is allowed, calculate the length of this sub-sequence.
Keep track of the maximum length found so far.
Once all possible starting points and lengths are checked, return the maximum length found.

Code Implementation

def max_consecutive_ones_brute_force(numbers, allowed_flips):
    maximum_length = 0

    for start_index in range(len(numbers)):
        for sub_sequence_length in range(1, len(numbers) - start_index + 1):
            end_index = start_index + sub_sequence_length
            sub_sequence = numbers[start_index:end_index]

            number_of_zeros = 0
            for number in sub_sequence:
                if number == 0:
                    number_of_zeros += 1

            # Checking if we have enough flips to make all the numbers one.
            if number_of_zeros <= allowed_flips:

                current_length = len(sub_sequence)
                # Keeping track of the maximum length.
                if current_length > maximum_length:

                    maximum_length = current_length

    # Returning the final result.
    return maximum_length

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible starting positions in the array, which is O(n). For each starting position, it iterates through all possible lengths of sub-sequences, resulting in another O(n) iteration. Inside this nested loop, it counts the number of zeros within the sub-sequence, which takes O(n) time in the worst case (scanning the sub-sequence). Thus the total time complexity is approximately n * n * n, which simplifies to O(n³).

Space Complexity

O(1) – The brute force approach only uses a few variables to track the starting point, length of the subsequence, the number of zeros within the subsequence, and the maximum length found so far. These variables occupy constant space regardless of the size of the input array. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The best way to solve this is to imagine a window that expands and contracts over the data. We try to make the window as big as possible while ensuring we don't use more allowed changes than we have available.

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

Imagine a sliding window that represents a section of the data.
Expand the window to the right, including more elements in the section.
Count how many changes (like flipping a zero to a one) are needed inside the window.
If the number of changes needed is more than we're allowed to make, shrink the window from the left until the number of changes needed is within the limit.
Keep track of the largest window you found that met the change limit.
Repeat the expand and shrink process until you've gone through all of the data.
The size of the largest window you found is the answer.

Code Implementation

def longestOnes(nums, max_flips):
    window_start = 0
    max_length = 0
    flipped_count = 0

    for window_end in range(len(nums)):
        if nums[window_end] == 0:
            flipped_count += 1

        # Shrink the window if flips exceed the limit
        while flipped_count > max_flips:

            if nums[window_start] == 0:
                flipped_count -= 1

            window_start += 1

        # Update the max length of valid window
        max_length = max(max_length, window_end - window_start + 1)

    return max_length

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums of size n using a sliding window approach. While the outer loop expands the window, the inner loop (shrinking the window) only executes a limited number of times relative to the overall input size. The left and right pointers each traverse the array at most once, meaning each element is visited a constant number of times. Thus, the time complexity is directly proportional to the size of the input array, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm uses a sliding window approach, primarily manipulating index variables to track the window's boundaries. It calculates the number of changes needed within the window but does not store this information in a data structure that scales with the input size N (where N is the length of the input array). The largest window size found is also stored in a single variable. Therefore, the space used remains constant regardless of the input size.

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there are no elements to form a subarray.
k is 0 and array contains zeros	The longest subarray will be the longest contiguous sequence of ones; iterate and keep track of the maximum such sequence.
k is greater than or equal to the number of zeros in the array	Return the length of the array because all zeros can be flipped to ones.
Array contains all ones (no zeros)	Return the length of the array, as no flips are needed.
Array contains all zeros and k is 0	Return 0 since no flips are allowed and no ones are present.
Large array size with a small k value (performance considerations)	The sliding window approach maintains O(n) time complexity, which is efficient even for large arrays.
k is a large value (approaching array length) but array is still very large	Sliding window adapts correctly and avoids integer overflow, since it only considers differences between indices within the current window.
Input array contains non-binary values	The solution should explicitly check if the input contains non-binary values (anything other than 0 or 1) and throw an exception or handle appropriately based on requirements.

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` and the maximum value of `k`?
Can the input array `nums` be empty or null?
If `k` is zero, and `nums` contains only zeros, what should the return value be?
Are the values in `nums` guaranteed to be only 0 or 1?
If there are multiple subarrays of the same maximum length after flipping at most `k` zeros, can I return the length of any of them?

Brute Force Solution

Approach

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

Consider every possible starting point in the sequence.
For each starting point, consider every possible length of the sub-sequence that begins there.
For each sub-sequence, count how many zeros are within it.
Check if the number of zeros within the sub-sequence is less than or equal to the allowed number of flips.
If the number of zeros is allowed, calculate the length of this sub-sequence.
Keep track of the maximum length found so far.
Once all possible starting points and lengths are checked, return the maximum length found.

Code Implementation

def max_consecutive_ones_brute_force(numbers, allowed_flips):
    maximum_length = 0

    for start_index in range(len(numbers)):
        for sub_sequence_length in range(1, len(numbers) - start_index + 1):
            end_index = start_index + sub_sequence_length
            sub_sequence = numbers[start_index:end_index]

            number_of_zeros = 0
            for number in sub_sequence:
                if number == 0:
                    number_of_zeros += 1

            # Checking if we have enough flips to make all the numbers one.
            if number_of_zeros <= allowed_flips:

                current_length = len(sub_sequence)
                # Keeping track of the maximum length.
                if current_length > maximum_length:

                    maximum_length = current_length

    # Returning the final result.
    return maximum_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine a sliding window that represents a section of the data.
Expand the window to the right, including more elements in the section.
Count how many changes (like flipping a zero to a one) are needed inside the window.
If the number of changes needed is more than we're allowed to make, shrink the window from the left until the number of changes needed is within the limit.
Keep track of the largest window you found that met the change limit.
Repeat the expand and shrink process until you've gone through all of the data.
The size of the largest window you found is the answer.

Code Implementation

def longestOnes(nums, max_flips):
    window_start = 0
    max_length = 0
    flipped_count = 0

    for window_end in range(len(nums)):
        if nums[window_end] == 0:
            flipped_count += 1

        # Shrink the window if flips exceed the limit
        while flipped_count > max_flips:

            if nums[window_start] == 0:
                flipped_count -= 1

            window_start += 1

        # Update the max length of valid window
        max_length = max(max_length, window_end - window_start + 1)

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return 0 immediately as there are no elements to form a subarray.
k is 0 and array contains zeros	The longest subarray will be the longest contiguous sequence of ones; iterate and keep track of the maximum such sequence.
k is greater than or equal to the number of zeros in the array	Return the length of the array because all zeros can be flipped to ones.
Array contains all ones (no zeros)	Return the length of the array, as no flips are needed.
Array contains all zeros and k is 0	Return 0 since no flips are allowed and no ones are present.
Large array size with a small k value (performance considerations)	The sliding window approach maintains O(n) time complexity, which is efficient even for large arrays.
k is a large value (approaching array length) but array is still very large	Sliding window adapts correctly and avoids integer overflow, since it only considers differences between indices within the current window.
Input array contains non-binary values	The solution should explicitly check if the input contains non-binary values (anything other than 0 or 1) and throw an exception or handle appropriately based on requirements.