Code Implementation

class Solution:
    def longestSubarray(self, nums):
        max_len = 0
        left = 0
        zero_count = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1
            while zero_count > 1:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            max_len = max(max_len, right - left)
        return max_len
      

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int maxLen = 0, left = 0, zeroCount = 0;
        for (int right = 0; right < nums.size(); ++right) {
            if (nums[right] == 0) zeroCount++;
            while (zeroCount > 1) {
                if (nums[left] == 0) zeroCount--;
                left++;
            }
            maxLen = max(maxLen, right - left);
        }
        return maxLen;
    }
};
      

class Solution {
    public int longestSubarray(int[] nums) {
        int maxLen = 0, left = 0, zeroCount = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zeroCount++;
            while (zeroCount > 1) {
                if (nums[left] == 0) zeroCount--;
                left++;
            }
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }
}
      

var longestSubarray = function(nums) {
    let maxLen = 0, left = 0, zeroCount = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) zeroCount++;
        while (zeroCount > 1) {
            if (nums[left] === 0) zeroCount--;
            left++;
        }
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
};
      

Problem Description

Given a binary array nums (an array containing only 0s and 1s), your task is to find the length of the longest contiguous subarray containing only 1s after deleting exactly one element from nums. You must remove one (and only one) element, which can be either a 0 or a 1. The subarray must be contiguous, and you cannot reuse elements (no overlapping). If the resulting array is empty, return 0.

• Only one element can be deleted.
• The input array can be large (up to 10⁵ elements).
• You must find the maximum possible length of a contiguous subarray of 1s after the deletion.

Thought Process

To solve this problem, the first idea might be brute force: for every index, try deleting that element and scan for the longest run of 1s. However, this would be too slow for large arrays. Instead, we want to find a way to efficiently track subarrays of 1s that can be formed by removing a single element.

The key insight is that deleting one element (ideally a 0) can join two runs of 1s, or simply extend a run by skipping a single 0. If we track the window between two 0s, we can always maintain at most one 0 in the window. If there are more than one 0, we move the left side of our window forward. This sliding window approach is much more efficient.

Solution Approach

• Sliding Window: Use two pointers, left and right, to define a window in the array.
• Keep a zero_count to track how many 0s are in the current window.
• Move right forward one step at a time. If nums[right] is 0, increment zero_count.
• If zero_count becomes more than 1, move left forward until there's only one 0 in the window.
• At each step, the length of the current valid window (with at most one 0) is right - left (not right - left + 1 because we must delete one element).
• Keep updating max_len with the maximum window length found.
• Return max_len at the end.

This approach efficiently finds the answer in a single pass through the array.

Example Walkthrough

Suppose nums = [1,1,0,1,1,1,0,1,1].

• Initialize: left = 0, zero_count = 0, max_len = 0
• Move right through the array:
• right = 0,1: Both are 1, so zero_count stays 0. max_len updates to 1, then 2.
• right = 2: nums[2] = 0, increment zero_count to 1. max_len is 2.
• right = 3,4,5: All 1s, window grows. max_len updates to 3, 4, 5.
• right = 6: nums[6] = 0, zero_count = 2. Now, move left forward until zero_count == 1:
  • Increment left to 3, skipping over 1,1,0. zero_count drops back to 1.
• Continue moving right to 7 and 8, updating max_len as needed.
• The maximum window found is length 5, corresponding to deleting one of the 0s and combining two runs of 1s.

Time and Space Complexity

• Brute-force: For each index, remove that element and scan the array for the longest run of 1s. For an array of length n, this is O(n²).
• Optimized (Sliding Window): Each element is visited at most twice (once by right, once by left), so the time complexity is O(n).
• Space complexity for both approaches is O(1), as only a few variables are used regardless of input size.

Summary

The problem asks for the longest contiguous subarray of 1s after deleting one element. The sliding window approach efficiently solves this by keeping at most one 0 in the window and dynamically adjusting the window size. This method is both simple and powerful, making it ideal for large input sizes. The key insight is realizing that deleting a 0 can join two runs of 1s, and that the window should always represent a possible answer after one deletion.