Log inSign up
mediumLeetCodeNot Started

Longest Subarray of 1's After Deleting One Element

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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 (0), [1,1,1] contains 3 numbers with value 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 (the middle 0), [0,1,1,1,1,1,0,1] longest subarray with value 1's is [1,1,1,1,1] which is length 5.

Example 3:

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sliding Window & Two Pointers technique
  • Dynamic state counting in contiguous subarrays
  • Max Consecutive Ones concepts

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Translate deletion-based problems into equivalent sliding window budget constraints.
  • Understand why a window with at most 1 zero has effective 1s length of (right - left).
  • Compare prefix/suffix array solutions O(N) space with two-pointer sliding window O(1) space.
  • Handle edge cases where all elements are 1s (must still delete one element, returning n - 1).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding the longest subarray of identical values with a budget of K deletions or flips (here K = 1).
  • Binary array input with contiguous sequence requirements.
  • Mandatory deletion constraint ("you must delete one element").

Algorithmic Decision Tree:

  • If checking all subarrays -> O(N2) brute force.
  • If finding longest contiguous subarray with at most 1 zero -> Sliding Window in O(N).
  • Result formula: Max(windowLength - 1) = Max(right - left).

Connected Patterns:

Max Consecutive Ones III (at most K zeros)Fruit Into BasketsConsecutive Characters

1. Brute Force (Nested Loop with Zero Counter)

Intuition

Try every possible starting index i. Expand rightwards with index j. Count how many zeros appear. If zeros <= 1, valid 1s length is j - i + 1 - zeros. Update max length.

Algorithm

  1. Step 1: Initialize maxLen = 0.
  2. Step 2: For each i from 0 to n - 1:
  3. - Initialize zeros = 0.
  4. - For each j from i to n - 1:
  5. - If nums[j] == 0, zeros++.
  6. - If zeros > 1, break.
  7. - maxLen = max(maxLen, j - i).
  8. Step 3: Return maxLen.

Brute Force (Nested Loop with Zero Counter) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 1, 0, 3, 12, 5]
Current operationSTEP 1 OF 6
Phase 1 — Setup: Left pointer L anchors at 0
Visual state
Values and pointers at this exact step
pointers
S
0
1
0
3
12
5
0
↑ L (Anchor)↑ R (Scan)
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Current Value
0
Valid Prefix Count
0
Check / comparison
arr[0]=0. Evaluate condition on first element.
Decision / next transition
Setup invariant: left pointer guards valid prefix.
Why this step matters

Phase 1 — Setup: Left pointer L anchors at 0. Scanner pointer R starts traversing the array.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int longestSubarray(std::vector<int>& nums) {
8 int n = nums.size();
9 int maxLen = 0;
10
11 for (int i = 0; i < n; i++) {
12 int zeros = 0;
13 for (int j = i; j < n; j++) {
14 if (nums[j] == 0) zeros++;
15 if (zeros > 1) break;
16 maxLen = std::max(maxLen, j - i);
17 }
18 }
19 return maxLen;
20 }
21};
22
23int main() {
24 Solution sol;
25 std::vector<int> nums = {1, 1, 0, 1};
26 std::cout << "Max 1s: " << sol.longestSubarray(nums) << std::endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (Nested Loop with Zero Counter).
  • Space complexity: O(1) — Space complexity for Brute Force (Nested Loop with Zero Counter).

Why Brute Force Doesn't Scale:

For N = 100,000, N2 = 1010 operations, taking over 10 seconds. Two-pointer sliding window guarantees that each element is touched at most twice, completing in 200,000 operations (< 5 ms).

For N = 100,000: Brute force takes ~10 billion operations; Sliding window takes ~200,000 operations.

2. Better (Prefix and Suffix Consecutive 1s Arrays)

Intuition

Precompute left[i] (consecutive 1s ending at i) and right[i] (consecutive 1s starting at i). For each index i, deleting nums[i] gives left[i - 1] + right[i + 1] consecutive 1s.

Algorithm

  1. Step 1: Compute left[i] as running consecutive 1s from left to right.
  2. Step 2: Compute right[i] as running consecutive 1s from right to left.
  3. Step 3: For each i from 0 to n - 1, compute (i > 0 ? left[i-1] : 0) + (i + 1 < n ? right[i+1] : 0) and maximize.
  4. Step 4: Return maxLen.

Prefix/Suffix Arrays on [1, 1, 0, 1]

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [nums = [1, 1, 0, 1]]
Current operationSTEP 1 OF 7
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
S
nums = [1, 1, 0, 1]
0
↑ i (Step 1)
Variables at this step
Current Phase
1
Inspected Value
nums = [1, 1, 0, 1]
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int longestSubarray(std::vector<int>& nums) {
8 int n = nums.size();
9 std::vector<int> left(n, 0), right(n, 0);
10
11 left[0] = (nums[0] == 1) ? 1 : 0;
12 for (int i = 1; i < n; i++) {
13 left[i] = (nums[i] == 1) ? left[i - 1] + 1 : 0;
14 }
15
16 right[n - 1] = (nums[n - 1] == 1) ? 1 : 0;
17 for (int i = n - 2; i >= 0; i--) {
18 right[i] = (nums[i] == 1) ? right[i + 1] + 1 : 0;
19 }
20
21 int maxLen = 0;
22 for (int i = 0; i < n; i++) {
23 int l = (i > 0) ? left[i - 1] : 0;
24 int r = (i + 1 < n) ? right[i + 1] : 0;
25 maxLen = std::max(maxLen, l + r);
26 }
27 return maxLen;
28 }
29};
30
31int main() {
32 Solution sol;
33 std::vector<int> nums = {1, 1, 0, 1};
34 std::cout << "Better Max 1s: " << sol.longestSubarray(nums) << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better (Prefix and Suffix Consecutive 1s Arrays).
  • Space complexity: O(N) — Space complexity for Better (Prefix and Suffix Consecutive 1s Arrays).

3. Optimal (Two-Pointer Sliding Window)

Intuition

Expand right. If nums[right] == 0, zeroCount++. While zeroCount > 1, if nums[left] == 0 zeroCount--, left++. Since 1 element is deleted from the window of length (right - left + 1), the number of 1s is (right - left). We track max(maxLen, right - left).

Algorithm

  1. Step 1: Initialize left = 0, zeros = 0, and maxLen = 0.
  2. Step 2: For right from 0 to nums.length - 1:
  3. - If nums[right] == 0, increment zeros.
  4. - While zeros > 1:
  5. - If nums[left] == 0, decrement zeros.
  6. - Increment left.
  7. - maxLen = max(maxLen, right - left).
  8. Step 3: Return maxLen.

Sliding Window on [0, 1, 1, 1, 0, 1, 1, 0, 1]

2 of 2 questions left today
Step 1 / 7
Trace timeline14% explored
InputINPUT nums = [nums = [0, 1, 1, 1, 0, 1, 1, 0, 1]]
Current operationSTEP 1 OF 7
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
S
nums = [0, 1, 1, 1, 0, 1, 1, 0, 1]
0
↑ i (Step 1)
Variables at this step
Current Phase
1
Inspected Value
nums = [0, 1, 1, 1, 0, 1, 1, 0, 1]
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 7
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int longestSubarray(std::vector<int>& nums) {
8 int left = 0;
9 int zeros = 0;
10 int maxLen = 0;
11
12 for (int right = 0; right < (int)nums.size(); right++) {
13 if (nums[right] == 0) {
14 zeros++;
15 }
16
17 while (zeros > 1) {
18 if (nums[left] == 0) {
19 zeros--;
20 }
21 left++;
22 }
23 maxLen = std::max(maxLen, right - left);
24 }
25 return maxLen;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::vector<int> nums = {0, 1, 1, 1, 0, 1, 1, 0, 1};
32 std::cout << "Optimal Max 1s: " << sol.longestSubarray(nums) << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal (Two-Pointer Sliding Window).
  • Space complexity: O(1) — Space complexity for Optimal (Two-Pointer Sliding Window).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Subarray Search with Zero Count)O(N^2)O(1)For every starting index i, expand j and count zeros. Stop when zeros > 1. Record max 1s count.Repeatedly scanning overlapping subarrays.
2.Better (Precomputing Left and Right Consecutive 1s)O(N)O(N)Precompute leftOnes[i] and rightOnes[i] for each index i. For each index i, if we delete it, consecutive 1s = leftOnes[i-1] + rightOnes[i+1].Extra memory allocation for prefix and suffix arrays.
3.Optimal (Sliding Window with 1 Zero Budget)OptimalO(N)O(1)Two pointers maintain a window with at most 1 zero. Track max window size - 1 in a single pass.Single pass scan bound.

Common Pitfalls & Crucial Edge Cases

Returning `right - left + 1` instead of `right - left`

The question strictly requires deleting one element, so the 1s count is always window size minus 1.

Returning `nums.length` when all elements are 1s

Deleting one element is mandatory even if no zeros exist in the input.

Shrinking `left` by jumping to the zero index without decrementing counters

A standard two-pointer while loop safely handles multiple consecutive zeros.

Crucial Edge Cases to Validate:

  • All 1s (nums = [1, 1, 1]): You MUST delete one element, returning n - 1 = 2. The formula right - left correctly gives 2 at the end.
  • All 0s (nums = [0, 0, 0]): Window size stays 1 zero, right - left yields 0.
  • Alternating 0s and 1s (nums = [1, 0, 1, 0, 1]): Window expands to span two 1s across one 0, yielding 2.
  • Single element (nums = [1] -> returns 0; nums = [0] -> returns 0).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Immediately clarify: "This problem is equivalent to Max Consecutive Ones with K = 1, where the answer is max window length minus 1."
  2. Highlight the edge case: When the input is all 1s [1,1,1], the answer is n - 1 = 2, which the right - left formula handles automatically without special if-checks.
  3. Explain the two-pointer monotonicity: Mention why both pointers only advance forward, guaranteeing strict O(N) linear time complexity.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the effective length of 1s calculated as right - left instead of right - left + 1?

2.What is the return value for nums = [1, 1, 1, 1] of length 4?

3.What is the time and auxiliary space complexity of the optimal sliding window approach?

Back to DSA Sheet