1493. Longest Subarray of 1's After Deleting One Element

Description

This algorithm solves the problem of finding the longest subarray of 1s after deleting at most one element from an array of binary integers. The goal is to determine the maximum length of a subarray that consists only of 1s, with the allowance to remove one 0.

Intuition

The problem can be approached by using a sliding window technique. The idea is to maintain a window that contains at most one zero at any time. By keeping track of the number of zeros in the current window, we can dynamically adjust the window size to ensure it remains valid (i.e., containing at most one zero). The length of the longest valid window is our answer.

Approach

1. Initialization: - Initialize variables to keep track of the count of zeros (z), the left pointer of the window (p1), and the maximum length of the window (lw).
2. Sliding Window: - Iterate through the array using a right pointer (i). For each element, increment the zero count if the element is 0. - If the zero count exceeds one, increment the left pointer (p1) until the window becomes valid again (zero count ≤ 1). - Update the maximum window length (lw) during each iteration.
3. Return the Result: - After processing the entire array, lw will contain the length of the longest subarray of 1s that can be achieved by removing at most one 0.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. We only pass through the array once.

Space Complexity:

O(1), as we use a constant amount of space regardless of the input size.

Code

C++

class Solution {
public:
    int longestSubarray(vector& nums) {
        int z = 0;
        int lw = 0;
        int p1 = 0;

        for (int i = 0; i < nums.size(); ++i) {
            z += (nums[i] == 0);

            while (z > 1) {
                z -= (nums[p1] == 0);
                p1++;
            }

            lw = max(lw, i - p1);
        }

        return lw;
    }
};

Python

class Solution:
    def longestSubarray(self, nums):
        z = 0
        lw = 0
        p1 = 0

        for i in range(len(nums)):
            z += (nums[i] == 0)

            while z > 1:
                z -= (nums[p1] == 0)
                p1 += 1

            lw = max(lw, i - p1)

        return lw

Java

class Solution {
    public int longestSubarray(int[] nums) {
        int z = 0;
        int lw = 0;
        int p1 = 0;

        for (int i = 0; i < nums.length; ++i) {
            z += (nums[i] == 0) ? 1 : 0;

            while (z > 1) {
                z -= (nums[p1] == 0) ? 1 : 0;
                p1++;
            }

            lw = Math.max(lw, i - p1);
        }

        return lw;
    }
}

JavaScript

var longestSubarray = function (nums) {
    let z = 0;
    let lw = 0;

    let p1 = 0;

    for (let i in nums) {
        z += (nums[i] === 0);

        while (z > 1) {
            z -= (nums[p1] == 0);
            p1++;
        }

        lw = Math.max(lw, i - p1);
    }

    return lw;
};