medium Longest Subarray of 1's After Deleting One Element

Problem Statement

Given a binary array nums, return the length of the longest non-empty subarray containing only 1's after removing 1 element from the array. Return 0 if there is no such subarray.

Examples

Example 1

• Input: [1, 1, 0, 0, 1, 1]
• Expected Output: 2
• Justification: By removing the first 0, you get [1, 1, 0, 1, 1] and the longest sequence of 1s is [1, 1].

Example 2

• Input: [1, 1, 0, 1, 1, 1]
• Expected Output: 5
• Justification: By removing the first 0, you get [1, 1, 1, 1, 1] which is the longest sequence of 1s .

Example 3

• Input: [1, 0, 1, 1, 0, 1]
• Expected Output: 3
• Justification: By removing the 0 between the first and third 1, you get [1, 1, 1, 0, 1], which has a length of 3.

Constraints:

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

Pattern

Variable window with must-delete-one. This is Max Consecutive Ones III with flip budget k = 1, but the problem requires deleting exactly one element, so the answer is window length minus 1: track maxLen = max(maxLen, right - left) (not + 1). Recognition: "longest 1s after deleting one element" / "at most one zero inside the window."

Edge: all ones → you still delete one, return n - 1. All zeros → after delete, empty of 1s → 0. Single element → 0.

Why right - left not right - left + 1: the window always "pays" for one deletion slot (the one zero allowed, or one 1 if there is no zero). Dropping the +1 encodes that forced deletion without a separate branch.

Solution

Maintain a window that contains at most one 0. Expand right; when a second 0 enters, advance left until only one 0 remains. Update the best length as right - left (window size minus the deleted element). One pass, O(n) time, O(1) space.

Step-by-Step Algorithm

1. Initialize Pointers and Variables:

   • Set two pointers, left and right, at the start of the list.
   • Create a variable zeroCount to count zeros in the current window.
   • Create a variable maxLen to store the maximum length of 1s found.

2. Iterate through the List:

   • Move the right pointer across the list.
   • If nums[right] is 0, increment zeroCount.

3. Adjust the Window:

   • If zeroCount exceeds 1, move the left pointer to the right until zeroCount is at most 1 again.
   • Adjust zeroCount accordingly by checking the value at nums[left].

4. Update Maximum Length:

   • Calculate the length of the current window (i.e., right - left).
   • Update maxLen if the current window length is greater.

5. Return Result:

   • Return maxLen, which is the maximum length of a subarray containing only 1s after removing one element.

Algorithm Walkthrough

Using the example input [1, 0, 1, 1, 0, 1]:

1. Initial State:

   • left = 0, right = 0, zeroCount = 0, maxLen = 0
   • Array: [1, 0, 1, 1, 0, 1]

2. Step 1:

   • Move right to 0.
   • nums[right] is 1, so zeroCount remains 0.
   • Current window: [1]
   • maxLen = max(0, 0 - 0) = 0
   • right moves to 1.

3. Step 2:

   • right at 1.
   • nums[right] is 0, so zeroCount increments to 1.
   • Current window: [1, 0]
   • maxLen = max(0, 1 - 0) = 1
   • right moves to 2.

4. Step 3:

   • right at 2.
   • nums[right] is 1, so zeroCount remains 1.
   • Current window: [1, 0, 1]
   • maxLen = max(1, 2 - 0) = 2
   • right moves to 3.

5. Step 4:

   • right at 3.
   • nums[right] is 1, so zeroCount remains 1.
   • Current window: [1, 0, 1, 1]
   • maxLen = max(2, 3 - 0) = 3
   • right moves to 4.

6. Step 5:

   • right at 4.
   • nums[right] is 0, so zeroCount increments to 2.
   • Since zeroCount > 1, adjust left.
     • nums[left] is 1, so zeroCount remains 2.
     • left moves to 1.
     • nums[left] is 0, so zeroCount decrements to 1.
     • left moves to 2.
   • Current window: [1, 1, 0, 1]
   • maxLen = max(3, 4 - 2) = 3
   • right moves to 5.

7. Step 6:

   • right at 5.
   • nums[right] is 1, so zeroCount remains 1.
   • Current window: [1, 1, 0, 1]
   • maxLen = max(3, 5 - 2) = 3
   • right moves to 6 (end of array).

8. Final State:

   • The maximum length of a subarray containing only 1s after removing one element is 3.

Code

class Solution {

  public int longestSubarray(int[] nums) {
    int left = 0, right = 0, zeroCount = 0, maxLen = 0;

    // Iterate through the array with right pointer
    while (right < nums.length) {
      if (nums[right] == 0) zeroCount++;

      // If more than one zero in the window, adjust left pointer
      while (zeroCount > 1) {
        if (nums[left] == 0) zeroCount--;
        left++;
      }

      // Update max length
      maxLen = Math.max(maxLen, right - left);
      right++;
    }

    return maxLen;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.longestSubarray(new int[] { 1, 1, 0, 0, 1, 1 })); // Output: 2
    System.out.println(sol.longestSubarray(new int[] { 1, 1, 0, 1, 1, 1 })); // Output: 5
    System.out.println(sol.longestSubarray(new int[] { 1, 0, 1, 1, 0, 1 })); // Output: 3
  }
}

Complexity Analysis

Time Complexity

The time complexity of the solution is , where n is the length of the input array nums. This is because we iterate through the array only once with the right pointer, and the left pointer also moves at most n times. Each element is processed a constant number of times, resulting in linear time complexity.

Space Complexity

The space complexity of the solution is . This is because we use a constant amount of extra space regardless of the size of the input array.

🎯 STRICT STANDOUT: Why / complexity derivation / pattern+when-not / edges / drills — Solution Longest Subarray of 1's After Deleting One Element

Why this exists (judgment layer)

Must-delete-one is Max Consecutive Ones III with k=1 plus a forced removal — the subtlety is encoding the delete as right−left (not +1) so all-ones still returns n−1.

Worked example & complexity derivation

nums=[1,0,1,1,0,1], k_zeros_allowed=1, must delete one element
Window may contain ≤1 zero; score = right-left  (= len-1)
Trace ends with best covering one zero + ones → score 3
All ones [1,1,1]: window full n, score n-1 (must delete a 1)
All zeros: after delete still no 1-run → 0
Time O(n) two pointers; space O(1)

Pattern transfer & when-NOT

Pattern: VARIABLE WINDOW, k=1 zero, answer = len−1. When-NOT: optional delete (then pure Ones III with k=1 keeps +1); delete up to k → Ones III; non-binary arrays → different constraint. Not fixed window.

Edge cases (hand-run)

Single element → 0. All ones → n−1. All zeros → 0. Two zeros only → longest ones after removing one zero may be short runs of ones.

Hostile-panel drills (defend the decision)

Q1. Why right−left not right−left+1?
Model answer: Problem forces deleting one element from the subarray/window; dropping +1 encodes that tax without a special case for 'zero vs one deleted'.

Q2. Hand-run [1,1,0,1,1,1] → 5.
Model answer: Window spanning the single zero has length 6; delete the zero → 5 ones.

Q3. Map to Ones III.
Model answer: Identical expand/shrink with k=1; answer transformation is −1 for mandatory delete.