Jobs

Interviews

Discussions

Longest Subarray of 1's After Deleting One Element #588 Most Asked

Medium

Microsoft

3 views

Topics:

ArraysSliding Windows

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

Constraints:

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

Try coding it in LeetCode

Longest Subarray of 1's After Deleting One Element #588 Most Asked

Medium

Microsoft

3 views

Topics:

ArraysSliding Windows

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1's in the resulting array. Return 0 if there is no such subarray.

Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1's.

Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

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 are the constraints on the size of the input array (e.g., maximum length)?
Can the input array contain values other than 0 and 1?
If the input array contains all zeros, what should the function return?
If the input array contains all ones, what should the function return?
If there are multiple subarrays of the same maximum length after deleting one element, is any of them acceptable?

Brute Force Solution

Approach

The brute force approach is all about trying every possible option. For this problem, we'll go through every place we could potentially remove a single zero and then see how long the longest string of ones becomes.

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

First, look at the original collection of ones and zeros.
Imagine removing the first zero you see. Count how many consecutive ones you have on either side of where you removed the zero. Add those counts together to see how many consecutive ones you would have.
Now, put that zero back where it was and remove the next zero in the collection. Again, count the ones on either side and add them up.
Keep doing this for every single zero you find in the original collection, each time calculating the total number of consecutive ones you would have after removing that particular zero.
If the collection contains no zeros, remove the first available one and count the remaining ones.
After you have done this for every possible zero (or the first one, if no zeros exist), compare all the totals you calculated. The largest total is the answer you are looking for: the length of the longest string of ones you can get after removing just one zero.

Code Implementation

def longest_subarray_of_ones_after_deleting_one_element_brute_force(numbers):
    maximum_length = 0
    zero_indices = [index for index, number in enumerate(numbers) if number == 0]

    # Handle the case where there are no zeros.
    if not zero_indices:
        return len(numbers) - 1

    for index_to_remove in zero_indices:
        left_count = 0
        right_count = 0

        # Count consecutive ones to the left.
        for left_index in range(index_to_remove - 1, -1, -1):
            if numbers[left_index] == 1:
                left_count += 1
            else:
                break

        # Count consecutive ones to the right.
        for right_index in range(index_to_remove + 1, len(numbers)):
            if numbers[right_index] == 1:
                right_count += 1
            else:
                break

        current_length = left_count + right_count
        maximum_length = max(maximum_length, current_length)

    return maximum_length

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size 'n' to identify the indices of all zeros. For each zero found, it calculates the length of the subarray of ones that would result from removing that specific zero. This calculation involves traversing the array segments to the left and right of the removed zero, potentially examining each of the remaining 'n' elements in the worst case. Therefore, in the worst-case scenario, where the array contains many zeros, the algorithm effectively performs 'n' operations for each zero, leading to approximately n * n operations. Thus the time complexity simplifies to O(n²).

Space Complexity

O(1) – The provided plain English explanation doesn't explicitly mention any auxiliary data structures like arrays, lists, or hashmaps. The steps involve iterating through the input, counting consecutive ones, and comparing totals. The intermediate counts and the maximum total found so far can be stored in a few constant space variables. Thus, the algorithm's space complexity is independent of the input size N (the number of elements in the input array). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The best way to solve this is by looking at parts of the sequence at a time. We keep track of how many '1's we see and how many '0's we have used up, always aiming to maximize the length of the '1's subarray we find after deleting one '0'.

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

Imagine you're sliding a window across the sequence of numbers.
Keep track of two things inside the window: how many '1's you've seen and how many '0's you've seen.
If you see a new '1', add it to your '1's count.
If you see a '0', add it to your '0's count.
If you have more than one '0' in your window, it means you need to shrink your window from the left side until you only have one '0' again.
While you're sliding the window, keep track of the biggest number of '1's you've seen in a window that contains at most one '0'. That's your longest possible subarray after deleting one element.
If the entire sequence consists of only 1s, you need to return the total number of ones minus 1.

Code Implementation

def longest_subarray_of_ones(nums):
    window_start = 0
    zero_count = 0
    max_ones = 0

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

        # Shrink the window until we have at most one zero
        while zero_count > 1:
            if nums[window_start] == 0:
                zero_count -= 1
            window_start += 1

        # Update the maximum length of the subarray
        max_ones = max(max_ones, window_end - window_start + 1)

    # If all elements are 1s, return length - 1
    if max_ones == len(nums):
        return max_ones - 1

    return max_ones

Big(O) Analysis

Time Complexity

O(n) – The algorithm uses a sliding window approach, where we iterate through the input array of size n once. Inside the loop, we adjust the window's start to maintain at most one zero within the window. This window adjustment also takes at most O(n) time across all iterations because the start pointer only moves forward. Therefore, the overall time complexity is dominated by the single pass through the array, resulting in O(n).

Space Complexity

O(1) – The algorithm uses a sliding window approach. It keeps track of the count of ones and zeros within the window using a few integer variables. These variables, such as counters for ones and zeros, and variables to track the window's start and end positions, occupy a constant amount of space irrespective of the input array's size, N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 if the input array is null or empty, as there are no elements to consider.
Array containing all 0s	Return 0, as deleting one 0 doesn't create a subarray of 1s.
Array containing all 1s	Return array length - 1, since we must delete one element, which will always be a 1.
Array with a single element	Return 0 if the single element is 1, otherwise return 0.
Array with only two elements	Handle this case by checking the values of the elements and returning appropriate value based on problem constraints.
Large input array to test efficiency	Ensure the solution uses a linear time complexity algorithm (e.g., sliding window) to handle large arrays efficiently.
Array with leading and trailing zeros	The sliding window approach correctly handles leading and trailing zeros by adjusting window boundaries accordingly.
Array with consecutive zeros	Sliding window should correctly update when it encounters consecutive zeroes and should not skip indices.

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 are the constraints on the size of the input array (e.g., maximum length)?
Can the input array contain values other than 0 and 1?
If the input array contains all zeros, what should the function return?
If the input array contains all ones, what should the function return?
If there are multiple subarrays of the same maximum length after deleting one element, is any of them acceptable?

Brute Force Solution

Approach

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

First, look at the original collection of ones and zeros.
Imagine removing the first zero you see. Count how many consecutive ones you have on either side of where you removed the zero. Add those counts together to see how many consecutive ones you would have.
Now, put that zero back where it was and remove the next zero in the collection. Again, count the ones on either side and add them up.
Keep doing this for every single zero you find in the original collection, each time calculating the total number of consecutive ones you would have after removing that particular zero.
If the collection contains no zeros, remove the first available one and count the remaining ones.
After you have done this for every possible zero (or the first one, if no zeros exist), compare all the totals you calculated. The largest total is the answer you are looking for: the length of the longest string of ones you can get after removing just one zero.

Code Implementation

def longest_subarray_of_ones_after_deleting_one_element_brute_force(numbers):
    maximum_length = 0
    zero_indices = [index for index, number in enumerate(numbers) if number == 0]

    # Handle the case where there are no zeros.
    if not zero_indices:
        return len(numbers) - 1

    for index_to_remove in zero_indices:
        left_count = 0
        right_count = 0

        # Count consecutive ones to the left.
        for left_index in range(index_to_remove - 1, -1, -1):
            if numbers[left_index] == 1:
                left_count += 1
            else:
                break

        # Count consecutive ones to the right.
        for right_index in range(index_to_remove + 1, len(numbers)):
            if numbers[right_index] == 1:
                right_count += 1
            else:
                break

        current_length = left_count + right_count
        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're sliding a window across the sequence of numbers.
Keep track of two things inside the window: how many '1's you've seen and how many '0's you've seen.
If you see a new '1', add it to your '1's count.
If you see a '0', add it to your '0's count.
If you have more than one '0' in your window, it means you need to shrink your window from the left side until you only have one '0' again.
While you're sliding the window, keep track of the biggest number of '1's you've seen in a window that contains at most one '0'. That's your longest possible subarray after deleting one element.
If the entire sequence consists of only 1s, you need to return the total number of ones minus 1.

Code Implementation

def longest_subarray_of_ones(nums):
    window_start = 0
    zero_count = 0
    max_ones = 0

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

        # Shrink the window until we have at most one zero
        while zero_count > 1:
            if nums[window_start] == 0:
                zero_count -= 1
            window_start += 1

        # Update the maximum length of the subarray
        max_ones = max(max_ones, window_end - window_start + 1)

    # If all elements are 1s, return length - 1
    if max_ones == len(nums):
        return max_ones - 1

    return max_ones

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 if the input array is null or empty, as there are no elements to consider.
Array containing all 0s	Return 0, as deleting one 0 doesn't create a subarray of 1s.
Array containing all 1s	Return array length - 1, since we must delete one element, which will always be a 1.
Array with a single element	Return 0 if the single element is 1, otherwise return 0.
Array with only two elements	Handle this case by checking the values of the elements and returning appropriate value based on problem constraints.
Large input array to test efficiency	Ensure the solution uses a linear time complexity algorithm (e.g., sliding window) to handle large arrays efficiently.
Array with leading and trailing zeros	The sliding window approach correctly handles leading and trailing zeros by adjusting window boundaries accordingly.
Array with consecutive zeros	Sliding window should correctly update when it encounters consecutive zeroes and should not skip indices.