1004. Max Consecutive Ones III

Description of Problem

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

1 <= nums.length <= 10^5
nums[i] is either 0 or 1.
0 <= k <= nums.length

Solution

Tags: Sliding Window Two Pointers

Explanation

Imagine that there is a double-linked list (deque) that stores 1s and at most k 0s. Loop over the array and do the following:

When 1 comes, put it into the back of deque
When 0 comes, there are two possible case:
1. The deque stores less than k 0s (i.e. the new 0 is available in the deque). In this case, put 0 into the the back of deque
2. The deque already stores k 0s. In this case, remove elements from the front of the deque until new 0 is available.

Code

impl Solution {
    pub fn longest_ones(nums: Vec<i32>, k: i32) -> i32 {
        let (n, k) = (nums.len(), k 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;
    }
}

Complexity

n is length of nums
X is the total number of elements pop from the deque

Time Complexity

\( T(n) = O(n) \)
- The time complexity is O(n+X) since the deque push n elements and pop X elements.
- X is less than or equal to n
- \(O(n+X) = O(2n) = O(n) \)

Auxiliary Space

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

Leetbook