Find the longest subarray with consecutive 1s if you can flip at most k zeros.

Medium

📘 Problem Statement

You are given a binary array (contains only 0s and 1s), and an integer k (maximum number of 0s you can flip to 1).

Find the length of the longest contiguous subarray that contains only 1s after flipping at most k zeros.

---

🔍 Example

Input :

nums = [1,1,0,0,1,1,1,0,1], k = 2

Output: : 7

(Flip the two 0s at index 2 and 3 → subarray becomes [1,1,1,1,1,1,1])

---

Intuition

This is a classic sliding window problem.

We want to keep a window where at most k zeros exist. We’ll expand the window to the right and shrink it from the left if zeros exceed k.

🛠️ Solution

🧮 Step-by-step Algorithm

• Initialize two pointers: left = 0, right = 0

• Track number of zeros in current window with zero_count

• Expand right one step at a time

• If zero_count > k, move left until it’s ≤ k

• Track the max window length during the process

🧑‍💻 Code

def longestOnes(nums: List[int], k: int) -> int:
    left = 0
    max_len = 0
    zero_count = 0

    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1

        while zero_count > k:
            if nums[left] == 0:
                zero_count -= 1
            left += 1  # shrink the window

        max_len = max(max_len, right - left + 1)

    return max_len

🕒 Time Complexity: \(O(n)\) - Each index is visited at most twice (once by right, once by left)

📦 Space Complexity: \(O(1)\) — no extra space used