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

Description of 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.

Example 1:

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's.

Example 2:

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

Example 3:

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.

Solution

Tags: Sliding Window Two Pointers

Explanation

If we solve 1004. Max Consecutive Ones III, we can use same code to solve this problem.

Remember to minus 1 before giving the answer. If there is no zeros, we have to minus one. If there is a zero, we also have to minus one.

Code

impl Solution {
    pub fn longest_subarray(nums: Vec<i32>) -> i32 {
        let (n, k) = (nums.len(), 1 as usize);
        let (mut i, mut j) = (0, 0);
        let mut count_zeros = 0;
        let mut max = 0;

        while j < n {
            if nums[j] == 0 {
                count_zeros+=1;
            }

            while count_zeros > k {
                if nums[i] == 0 { count_zeros-=1; }
                i+=1;
            }
            max = max.max(j - i + 1);
            j+=1;
        }

        return max as i32 - 1;
    }

}

Complexity

n is length of nums

Time Complexity

\( T(n) = O(n) \)

Auxiliary Space

\( S(n) = O(1) \)

Leetbook