1004. Max Consecutive Ones III

Description

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 <= 105
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

Solutions

Solution 1: Sliding Window

We define a sliding window, the number of $0$s in the window does not exceed $k$. The right boundary of the window keeps moving to the right. When the number of $0$s in the window exceeds $k$, the left boundary of the window moves to the right until the number of $0$s in the window does not exceed $k$.

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

Similar problems:

• 487. Max Consecutive Ones II
• 2024. Maximize the Confusion of an Exam

Python3JavaC++GoTypeScript

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        ans = 0
        cnt = j = 0
        for i, v in enumerate(nums):
            if v == 0:
                cnt += 1
            while cnt > k:
                if nums[j] == 0:
                    cnt -= 1
                j += 1
            ans = max(ans, i - j + 1)
        return ans

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

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

func longestOnes(nums []int, k int) int {
    ans := 0
    j, cnt := 0, 0
    for i, v := range nums {
        if v == 0 {
            cnt++
        }
        for cnt > k {
            if nums[j] == 0 {
                cnt--
            }
            j++
        }
        ans = max(ans, i-j+1)
    }
    return ans
}

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

Solution 2: Sliding Window (Optimized)

Below is the optimized version of the sliding window.

Maintain a monotonically variable-length window. This kind of window often appears in problems seeking the "maximum window": because we are seeking the "maximum", there is no need to shorten the window, so the code lacks the part to shorten the window; from another perspective, the K in this problem is the number of resources, once overdrawn, the window can no longer grow.

• l is the left endpoint of the window, responsible for moving the starting position
• r is the right endpoint of the window, responsible for expanding the window
• k is the number of resources, each time a 0 needs to be replaced, k decreases by 1, and r moves to the right at the same time
• r++ will be executed every time, l++ is only triggered when the resource k < 0, therefore the value of r - l will only increase monotonically (or remain unchanged)
• When moving the left endpoint, if the current element is 0, it means that a resource can be released, k increases by 1

The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.

Python3JavaC++GoTypeScriptRust

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = r = -1
        while r < len(nums) - 1:
            r += 1
            if nums[r] == 0:
                k -= 1
            if k < 0:
                l += 1
                if nums[l] == 0:
                    k += 1
        return r - l

class Solution {
    public int longestOnes(int[] nums, int k) {
        int l = 0, r = 0;
        while (r < nums.length) {
            if (nums[r++] == 0) {
                --k;
            }
            if (k < 0 && nums[l++] == 0) {
                ++k;
            }
        }
        return r - l;
    }
}

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int l = 0, r = 0;
        while (r < nums.size()) {
            if (nums[r++] == 0) --k;
            if (k < 0 && nums[l++] == 0) ++k;
        }
        return r - l;
    }
};

func longestOnes(nums []int, k int) int {
    l, r := -1, -1
    for r < len(nums)-1 {
        r++
        if nums[r] == 0 {
            k--
        }
        if k < 0 {
            l++
            if nums[l] == 0 {
                k++
            }
        }
    }
    return r - l
}

function longestOnes(nums: number[], k: number): number {
    const n = nums.length;
    let l = 0;
    for (const num of nums) {
        if (num === 0) {
            k--;
        }
        if (k < 0 && nums[l++] === 0) {
            k++;
        }
    }
    return n - l;
}

impl Solution {
    pub fn longest_ones(nums: Vec<i32>, mut k: i32) -> i32 {
        let n = nums.len();
        let mut l = 0;
        for num in nums.iter() {
            if num == &0 {
                k -= 1;
            }
            if k < 0 {
                if nums[l] == 0 {
                    k += 1;
                }
                l += 1;
            }
        }
        (n - l) as i32
    }
}

Comments