Problem: Longest Subarray of 1's After Deleting One Element

Given a binary array nums, find the length of the longest subarray containing only 1s after deleting at most one element.

Approach 1: Enumeration

This approach iterates through each element in the array, considering it as the element to be deleted. For each deletion, it calculates the length of the longest subarray of 1s.

Algorithm:

1. Preprocessing: Create two arrays, left and right. left[i] stores the length of the longest consecutive 1s subarray ending at index i. Similarly, right[i] stores the length of the longest consecutive 1s subarray starting at index i.

2. Iteration: Iterate through the array. For each index i, consider deleting the element at that index. The length of the longest subarray of 1s after deletion is left[i-1] + right[i+1]. Update the maximum length found so far.

3. Return: Return the maximum length found.

Time Complexity: O(n), due to single pass through the array for preprocessing and iteration. Space Complexity: O(n), due to the left and right arrays.

Approach 2: Two Pointers (Sliding Window)

This approach uses a sliding window to efficiently find the longest subarray with at most one 0.

Algorithm:

1. Initialize ans (maximum length), cnt (count of 0s), and j (left pointer) to 0.
2. Iterate with i (right pointer) through the array:
   • If nums[i] == 0, increment cnt.
   • While cnt > 1, decrement cnt (by removing elements from the left) and increment j.
   • Update ans with max(ans, i - j + 1).
3. Return ans.

Time Complexity: O(n), as each element is visited at most twice (once by i and once by j). Space Complexity: O(1), as it uses only a few constant extra variables.

Approach 3: Two Pointers (Optimized)

This is a slight optimization over Approach 2. Instead of repeatedly moving the left pointer (j) until cnt <= 1, it moves it only once when cnt exceeds 1. This avoids unnecessary iterations while maintaining correctness.

Algorithm:

1. Initialize cnt (count of 0s), l (left pointer) to 0.
2. Iterate through the array:
   • If nums[i] == 0, increment cnt.
   • If cnt > 1, move the left pointer l and adjust cnt accordingly.
3. The final answer is len(nums) - l - 1.

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

Code Examples

The code examples below demonstrate Approach 2 (Two Pointers) in various languages due to its efficiency and clarity. Approach 3 offers a minor optimization. Approach 1, while correct, is less efficient.

Python

def longestSubarray(nums):
    ans = 0
    cnt = j = 0
    for i, x in enumerate(nums):
        cnt += x ^ 1  # Efficiently counts 0s (x ^ 1 is 1 if x is 0, 0 otherwise)
        while cnt > 1:
            cnt -= nums[j] ^ 1
            j += 1
        ans = max(ans, i - j + 1)
    return ans
 

Java

class Solution {
    public int longestSubarray(int[] nums) {
        int ans = 0;
        int cnt = 0;
        int j = 0;
        for (int i = 0; i < nums.length; ++i) {
            cnt += nums[i] ^ 1;
            while (cnt > 1) {
                cnt -= nums[j++] ^ 1;
            }
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }
}

C++

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int ans = 0;
        int cnt = 0;
        int j = 0;
        for (int i = 0; i < nums.size(); ++i) {
            cnt += nums[i] ^ 1;
            while (cnt > 1) {
                cnt -= nums[j++] ^ 1;
            }
            ans = max(ans, i - j + 1);
        }
        return ans;
    }
};

JavaScript

const longestSubarray = (nums) => {
    let ans = 0;
    let cnt = 0;
    let j = 0;
    for (let i = 0; i < nums.length; ++i) {
        cnt += nums[i] ^ 1;
        while (cnt > 1) {
            cnt -= nums[j++] ^ 1;
        }
        ans = Math.max(ans, i - j + 1);
    }
    return ans;
};

These code examples all implement the efficient two-pointer approach. Remember to choose the language most suitable for your needs. The time complexity remains O(n) and space complexity O(1) for all these implementations.