Longest Subarray of 1's After Deleting One Element

medium 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.

Inputnums = [1,1,0,1,1,1,0,1]

Output5

Window [0..5] has length 6 with one zero — after deletion run length = 5.

nums (binary, comma-separated)

def longest_subarray(nums):
    l = zeros = best = 0
    for r, x in enumerate(nums):
        if x == 0: zeros += 1
        while zeros > 1:
            if nums[l] == 0: zeros -= 1
            l += 1
        if r - l > best: best = r - l
    return best

function longestSubarray(nums) {
  let l = 0, zeros = 0, best = 0;
  for (let r = 0; r < nums.length; r++) {
    if (nums[r] === 0) zeros++;
    while (zeros > 1) {
      if (nums[l] === 0) zeros--;
      l++;
    }
    if (r - l > best) best = r - l;
  }
  return best;
}

class Solution {
    public int longestSubarray(int[] nums) {
        int l = 0, zeros = 0, best = 0;
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] == 0) zeros++;
            while (zeros > 1) {
                if (nums[l] == 0) zeros--;
                l++;
            }
            if (r - l > best) best = r - l;
        }
        return best;
    }
}

int longestSubarray(vector<int>& nums) {
    int l = 0, zeros = 0, best = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        if (nums[r] == 0) zeros++;
        while (zeros > 1) {
            if (nums[l] == 0) zeros--;
            l++;
        }
        if (r - l > best) best = r - l;
    }
    return best;
}

Explanation

Since we must delete exactly one element, the best we can hope for is a stretch of 1s that contains at most one 0 — deleting that 0 (or any element if there are none) leaves a clean run of 1s.

So we slide a window that is allowed to hold at most one zero. We move the right edge r forward and count zeros inside. The moment zeros > 1, we advance the left edge l until we've dropped a zero back out.

The answer for any valid window is r - l, not r - l + 1, because one element is always removed by the deletion. Using r - l automatically accounts for that single deleted slot.

Example: nums = [1,1,0,1,1,1,0,1]. The window [0..5] = 1,1,0,1,1,1 has length 6 with exactly one zero, so after deleting the zero the run is r - l = 5, which is the answer.

Each index is visited by r once and by l at most once, giving linear time and constant extra space.

Time: O(n) Space: O(1)