[/dsa/leetcode]

1493 - Longest Subarray of 1s After Deleting One Element

Thursday, 17 September 2026

<medium> [problem]

Sliding window holding at most one zero, with the window length minus one as the answer.

{array}{sliding window}

Problem

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.

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

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] has the longest subarray
with value of 1's is [1,1,1,1,1]

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

Constraints:

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

Approach

Deleting one element means the part we keep can hold one zero, the one we delete. So we want the longest stretch with at most one zero in it. Move r forward across the array and count the zeros inside the window. When there are two, move l forward until one of them is gone. The answer for a window is its length minus one, because one element always has to go. That gives r - l instead of r - l + 1, and it also handles an array of all ones on its own: no window ever holds a zero, so we end with n - 1, which is what deleting one 1 leaves behind.

nums = [0,1,1,1,0,1,1,0,1]
r=0  [0]              zeros=1                  best=0
r=1  [0,1]            zeros=1                  best=1
r=2  [0,1,1]          zeros=1                  best=2
r=3  [0,1,1,1]        zeros=1                  best=3
r=4  [0,1,1,1,0]      zeros=2 -> drop the 0    best=3
     [1,1,1,0]        zeros=1
r=5  [1,1,1,0,1]      zeros=1                  best=4
r=6  [1,1,1,0,1,1]    zeros=1                  best=5
r=7  [1,1,1,0,1,1,0]  zeros=2 -> drop the 0    best=5
     [1,1,0,1]        zeros=1
r=8  [1,1,0,1,1]      zeros=1                  best=5
answer = 5
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        const int n = nums.size();
        int maxi = 0;
        int zeros = 0;
        for (int r = 0, l = 0; r < n; r++) {
            if (nums[r] == 0)
                zeros++;
            while (zeros > 1) {
                if (nums[l] == 0)
                    zeros--;
                l++;
            }
            maxi = max(maxi, r - l);
        }
        return maxi;
    }
};

1004 is the same window with room for k zeros instead of one, and it uses r - l + 1, since nothing has to be deleted there.

  • time: O(n) - each element is added once and removed at most once
  • space: O(1)
quantinium © 2026