Problem Description

You are given a binary array nums (containing only 0s and 1s). You must delete exactly one element from this array.

After deleting one element, you need to find the longest subarray that contains only 1s. Return the length of this longest subarray. If no such subarray exists after deletion, return 0.

For example:

• If nums = [1,1,0,1], after deleting the element at index 2 (the 0), we get [1,1,1], which gives us a subarray of length 3 containing only 1s.
• If nums = [0,1,1,1,0,1,1,0,1], we could delete the element at index 4 (the 0), which would connect the 1s on both sides, giving us [1,1,1,1,1] as the longest subarray of 1s with length 5.
• If nums = [1,1,1], we must still delete one element. After deleting any 1, we're left with a subarray of length 2 containing only 1s.

The key insight is that deleting an element can potentially connect two groups of consecutive 1s if we delete a 0 between them, or it will simply reduce the length of a group of 1s if we delete a 1.

Intuition

The key observation is that when we delete an element at position i, we're essentially trying to connect the consecutive 1s that appear before position i with the consecutive 1s that appear after position i.

Think about what happens when we delete different types of elements:

• If we delete a 0, we can potentially join two groups of 1s that were separated by this 0
• If we delete a 1, we break a sequence of 1s, but we still get the remaining 1s on either side

For any position i that we choose to delete, the resulting length of consecutive 1s would be:

• The number of consecutive 1s ending right before position i
• Plus the number of consecutive 1s starting right after position i

This leads us to think about preprocessing the array. If we can know for each position:

1. How many consecutive 1s end at or before this position (let's call this left[i])
2. How many consecutive 1s start at or after this position (let's call this right[i])

Then for each deletion position i, we can quickly calculate the result as left[i] + right[i+1].

The preprocessing approach makes sense because:

• left[i] can be computed by scanning from left to right: if nums[i] is 1, then left[i] = left[i-1] + 1, otherwise it's 0
• right[i] can be computed by scanning from right to left: if nums[i] is 1, then right[i] = right[i+1] + 1, otherwise it's 0

By trying all possible deletion positions and taking the maximum, we get our answer. This transforms a potentially complex problem into a simple enumeration with preprocessing.

Learn more about Dynamic Programming and Sliding Window patterns.

Solution Approach

The solution uses a preprocessing approach with two auxiliary arrays to efficiently calculate the result for each possible deletion position.

Step 1: Initialize auxiliary arrays

We create two arrays left and right, both of size n+1 (where n is the length of nums). These arrays are initialized with zeros:

• left[i] will store the count of consecutive 1s ending at position i-1 in the original array
• right[i] will store the count of consecutive 1s starting at position i in the original array

Step 2: Build the left array

We iterate through nums from left to right (using 1-based indexing for left):

for i, x in enumerate(nums, 1):
    if x:
        left[i] = left[i - 1] + 1

• If nums[i-1] is 1, then left[i] = left[i-1] + 1 (extending the consecutive 1s)
• If nums[i-1] is 0, then left[i] remains 0 (breaking the sequence)

Step 3: Build the right array

We iterate through nums from right to left:

for i in range(n - 1, -1, -1):
    if nums[i]:
        right[i] = right[i + 1] + 1

• If nums[i] is 1, then right[i] = right[i+1] + 1 (extending the consecutive 1s from the right)
• If nums[i] is 0, then right[i] remains 0

Step 4: Calculate the maximum

For each position i that we could delete (from 0 to n-1), we calculate:

• left[i]: consecutive 1s ending just before position i
• right[i+1]: consecutive 1s starting just after position i
• The sum left[i] + right[i+1] gives us the length of consecutive 1s after deleting element at position i

We return the maximum value among all possible deletion positions:

return max(left[i] + right[i + 1] for i in range(n))

Time Complexity: O(n) - We make three passes through the array Space Complexity: O(n) - We use two auxiliary arrays of size n+1

Example Walkthrough

Let's walk through the solution with nums = [1,1,0,1,0,1,1].

Step 1: Initialize arrays

• n = 7
• left = [0,0,0,0,0,0,0,0] (size 8)
• right = [0,0,0,0,0,0,0,0] (size 8)

Step 2: Build the left array

Processing from left to right:

• Index 0: nums[0] = 1, so left[1] = left[0] + 1 = 0 + 1 = 1
• Index 1: nums[1] = 1, so left[2] = left[1] + 1 = 1 + 1 = 2
• Index 2: nums[2] = 0, so left[3] = 0 (sequence breaks)
• Index 3: nums[3] = 1, so left[4] = left[3] + 1 = 0 + 1 = 1
• Index 4: nums[4] = 0, so left[5] = 0 (sequence breaks)
• Index 5: nums[5] = 1, so left[6] = left[5] + 1 = 0 + 1 = 1
• Index 6: nums[6] = 1, so left[7] = left[6] + 1 = 1 + 1 = 2

Result: left = [0,1,2,0,1,0,1,2]

Step 3: Build the right array

Processing from right to left:

• Index 6: nums[6] = 1, so right[6] = right[7] + 1 = 0 + 1 = 1
• Index 5: nums[5] = 1, so right[5] = right[6] + 1 = 1 + 1 = 2
• Index 4: nums[4] = 0, so right[4] = 0 (sequence breaks)
• Index 3: nums[3] = 1, so right[3] = right[4] + 1 = 0 + 1 = 1
• Index 2: nums[2] = 0, so right[2] = 0 (sequence breaks)
• Index 1: nums[1] = 1, so right[1] = right[2] + 1 = 0 + 1 = 1
• Index 0: nums[0] = 1, so right[0] = right[1] + 1 = 1 + 1 = 2

Result: right = [2,1,0,1,0,2,1,0]

Step 4: Calculate maximum for each deletion position

For each index i, calculate left[i] + right[i+1]:

• Delete index 0: left[0] + right[1] = 0 + 1 = 1
• Delete index 1: left[1] + right[2] = 1 + 0 = 1
• Delete index 2: left[2] + right[3] = 2 + 1 = 3 ✓ (connects two 1s with one 1)
• Delete index 3: left[3] + right[4] = 0 + 0 = 0
• Delete index 4: left[4] + right[5] = 1 + 2 = 3 ✓ (connects one 1 with two 1s)
• Delete index 5: left[5] + right[6] = 0 + 1 = 1
• Delete index 6: left[6] + right[7] = 1 + 0 = 1

Maximum value: 3

This makes sense! When we delete either the 0 at index 2 or the 0 at index 4, we can connect groups of 1s to get a maximum length of 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of three main parts:

• First loop: Iterates through the array once to populate the left array, taking O(n) time
• Second loop: Iterates through the array once in reverse to populate the right array, taking O(n) time
• Final computation: Iterates through all indices to find the maximum of left[i] + right[i + 1], taking O(n) time

Since these operations are sequential and not nested, the overall time complexity is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses additional space for:

• left array of size n + 1
• right array of size n + 1

Both arrays store intermediate results, requiring O(n + 1) + O(n + 1) = O(n) extra space in total.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting the Mandatory Deletion Requirement

A common mistake is not handling the case where the array contains only 1s. In this scenario, we still must delete exactly one element, so the maximum length should be n-1, not n.

Incorrect approach:

# This would incorrectly return n for an array of all 1s
return max(left[i] + right[i + 1] for i in range(n))

Why it fails: For nums = [1,1,1], this would calculate:

• Position 0: left[0] + right[1] = 0 + 2 = 2
• Position 1: left[1] + right[2] = 1 + 1 = 2
• Position 2: left[2] + right[3] = 2 + 0 = 2

The result is correct (2), but only by coincidence due to how the arrays are built.

2. Off-by-One Errors in Array Indexing

The solution uses 1-based indexing for the left array but 0-based for right, which can be confusing and lead to errors.

Common mistake:

# Incorrect: mixing up the indexing
for i in range(n):
    if nums[i]:
        left[i] = left[i - 1] + 1  # Wrong! This would access left[-1] when i=0

Solution: Be consistent with indexing or clearly document the offset:

# Correct: using enumerate with start=1 for clarity
for i, num in enumerate(nums, 1):
    if num == 1:
        left[i] = left[i - 1] + 1

3. Not Initializing Arrays with Correct Size

Incorrect:

left = [0] * n  # Wrong size!
right = [0] * n

This would cause an index out of bounds error when accessing right[n] or when building the left array.

Solution: Always use size n+1 for both arrays to accommodate the boundary conditions:

left = [0] * (n + 1)
right = [0] * (n + 1)

4. Alternative Sliding Window Approach Pitfall

Some might attempt a sliding window approach tracking zeros, but forget to handle the edge case where there are no zeros in the array:

Problematic sliding window:

def longestSubarray(self, nums):
    zero_count = 0
    left = 0
    max_len = 0
  
    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1
      
        while zero_count > 1:  # Allow at most 1 zero
            if nums[left] == 0:
                zero_count -= 1
            left += 1
      
        max_len = max(max_len, right - left + 1)
  
    return max_len - 1  # Subtract 1 for the deletion

Why it fails: For nums = [1,1,1] with no zeros, this would return 3 - 1 = 2, which is correct. However, the logic is unclear and the -1 at the end seems arbitrary. A better approach would explicitly check if any zeros exist:

# Better: explicitly handle the all-1s case
if 0 not in nums:
    return len(nums) - 1
# ... rest of sliding window logic