Crack the Backend

Problem Statement

Given a binary array nums (each element is 0 or 1) and an integer k, return the maximum number of consecutive 1's you can obtain by flipping at most k zeros to 1's.

You are allowed to flip at most k zeros to ones; after that, find the longest contiguous segment of 1's.
The array is not modified in place for the purpose of counting — we are conceptually asking: "what is the longest contiguous block of 1's we can get if we flip at most k zeros?"
k can be 0 (no flips); then the answer is the longest existing run of 1's.

Key Observations

We can model this as a sliding window where we allow at most k zeros inside the window. The "consecutive 1's" after flipping up to k zeros is exactly the window length when we allow at most k zeros.
Expand with right; when the number of zeros in the window exceeds k, shrink left until we have at most k zeros again. At each step the window has at most k zeros, so it represents a valid "consecutive 1's" segment (after flipping those zeros).
The maximum window size over the scan is the answer.

Approach

High-level: Maintain a window [left, right] that contains at most k zeros. Expand with right; if zeros exceed k, shrink left until zeros <= k. Track the maximum window size.

Steps:

left = 0, zeros = 0, best = 0.
For each right: if nums[right] == 0, increment zeros. While zeros > k, if nums[left] == 0 decrement zeros, then left++.
best = max(best, right - left + 1). Return best.

Implementation

Java

public int longestOnes(int[] nums, int k) {
    int left = 0, zeros = 0, best = 0;

    for (int right = 0; right < nums.length; right++) {
        if (nums[right] == 0) {
            zeros++;
        }

        while (zeros > k) {
            if (nums[left] == 0) {
                zeros--;
            }

            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}

Test Cases

Example 1

Input

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

Expected

6

Explanation

Flip two zeros in the middle.

Complexity Analysis

Time: O(n).
Space: O(1).

Follow-ups

Minimize the number of flips for a given window length.