Max Consecutive Ones III

LeetCode 1046 | Difficulty: Medium

Medium

Problem 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 <= 10^5`

- `nums[i]` is either `0` or `1`.

- `0 <= k <= nums.length`

Topics: Array, Binary Search, Sliding Window, Prefix Sum

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 168 ms)

Metric	Value
Runtime	168 ms
Memory	37.1 MB
Date	2019-03-17

Solution

public class Solution {
    public int LongestOnes(int[] A, int K) {
            int result=0, start=0, end, counter=0;
    for (end = 0; end < A.Length; end++)
    {
        if(A[end]==0) counter++;
        while(counter > K)
        {
            if(A[start]==0) counter--;
            start++;
        }
        result = Math.Max(result, end-start+1);
    }
    
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$
Sliding Window	$O(n)$	$O(k)$
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Precisely define what the left and right boundaries represent, and the loop invariant.
• LeetCode provides 4 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: One thing's for sure, we will only flip a zero if it extends an existing window of 1s. Otherwise, there's no point in doing it, right? Think Sliding Window!

Hint 2: Since we know this problem can be solved using the sliding window construct, we might as well focus in that direction for hints. Basically, in a given window, we can never have > K zeros, right?

Hint 3: We don't have a fixed size window in this case. The window size can grow and shrink depending upon the number of zeros we have (we don't actually have to flip the zeros here!).

Hint 4: The way to shrink or expand a window would be based on the number of zeros that can still be flipped and so on.