Problem

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

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

Method 1 – Sliding Window with At Most k Zero Flips

Intuition

We want the longest sequence of 1s, allowing at most k zeros to be flipped to 1. By using a sliding window, we can efficiently track the window containing at most k zeros and update the maximum length found.

Approach

  1. Initialize two pointers l and r for the window, and a variable zero to count zeros in the window.
  2. Move the right pointer r through the array:
    • If nums[r] is 0, increment zero.
    • If zero exceeds k, move the left pointer l right until zero is at most k.
    • Update the answer with the current window size.
  3. Return the maximum window size found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int l = 0, ans = 0, zero = 0;
        for (int r = 0; r < nums.size(); ++r) {
            if (nums[r] == 0) zero++;
            while (zero > k) {
                if (nums[l++] == 0) zero--;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func longestOnes(nums []int, k int) int {
    l, ans, zero := 0, 0, 0
    for r, x := range nums {
        if x == 0 {
            zero++
        }
        for zero > k {
            if nums[l] == 0 {
                zero--
            }
            l++
        }
        if r-l+1 > ans {
            ans = r-l+1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int longestOnes(int[] nums, int k) {
        int l = 0, ans = 0, zero = 0;
        for (int r = 0; r < nums.length; r++) {
            if (nums[r] == 0) zero++;
            while (zero > k) {
                if (nums[l++] == 0) zero--;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun longestOnes(nums: IntArray, k: Int): Int {
        var l = 0
        var ans = 0
        var zero = 0
        for (r in nums.indices) {
            if (nums[r] == 0) zero++
            while (zero > k) {
                if (nums[l++] == 0) zero--
            }
            ans = maxOf(ans, r - l + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def longestOnes(self, nums: list[int], k: int) -> int:
        l = ans = zero = 0
        for r, x in enumerate(nums):
            if x == 0:
                zero += 1
            while zero > k:
                if nums[l] == 0:
                    zero -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn longest_ones(nums: Vec<i32>, k: i32) -> i32 {
        let (mut l, mut ans, mut zero) = (0, 0, 0);
        for (r, &x) in nums.iter().enumerate() {
            if x == 0 {
                zero += 1;
            }
            while zero > k {
                if nums[l] == 0 {
                    zero -= 1;
                }
                l += 1;
            }
            ans = ans.max(r as i32 - l as i32 + 1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    longestOnes(nums: number[], k: number): number {
        let l = 0, ans = 0, zero = 0;
        for (let r = 0; r < nums.length; r++) {
            if (nums[r] === 0) zero++;
            while (zero > k) {
                if (nums[l++] === 0) zero--;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the array, since we scan the array once.
  • 🧺 Space complexity: O(1), as only a few variables are used.