DSA sheet · Arrays · Sliding Window pattern (variable size, longest)

Max Consecutive Ones III

The "part three" of Max Consecutive Ones: now you may flip up to k zeros into ones. The teacher solves it three times: a brute force (O(n²)), a better sliding window that shrinks with a while loop (she calls it O(2n)), and the most optimised version where the left pointer moves with an if, at most one step per step of right, so the window never gets smaller, and the answer is simply n − left.

Why it matters: this is the standard "longest window with at most k bad cells" problem (Pattern 4 in the overview). The same code, with "bad cell" redefined, solves Longest Repeating Character Replacement, Fruits Into Baskets and more. And the never-shrinking window trick is a favourite follow-up question in interviews.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Sliding window from scratch
• Part A · Brute force: every start, count zeros
• Part B · Better: sliding window, shrink with while (O(2n))
• Part C · Most optimised: shift with if, return n − left (O(n))
• Part D · Revision page

Part 0 · Before starting

Window, expand, shrink

A subarray = a contiguous piece of the array = a window [left..right], both ends included, length right − left + 1. The brute force tries every start and re-walks overlapping windows: O(n²). A sliding window moves right forward once over the array (expand: a cell joins) and moves left forward only when needed (shrink: the oldest cell leaves). Neither moves back.

Fixed vs variable

Careful: in this problem k is not a window size. It's the number of zeros you may flip. The window size is free.

Other shapes in this notebook: shortest valid (record while shrinking), count of valid windows (count += right − left + 1), and "exactly K = atMost(K) − atMost(K − 1)". All of them need a one-way condition, and here we have one: the number of zeros in a window can only go up when it grows and down when it shrinks. So once a window has too many zeros, growing can't fix it; only shrinking can. (Sum problems lose this property when negatives are allowed.)

The "bad cell" counter

We don't need a full frequency map here: the only thing that matters is how many zeros are inside. One integer, zero_count, plays the role of the map. +1 when a 0 joins, −1 when a 0 leaves. The window is valid while zero_count ≤ k, because then we can flip all its zeros.

Part A · Brute force: every start, count zeros

LeetCode 1004

1The question in simple words

You get a binary array nums (every value is 0 or 1) and an integer k. You may change at most k zeros into ones. Return the longest run of consecutive 1s you can end up with.

Another way to say it: find the longest window that contains at most k zeros. Flip those zeros and the whole window is 1s.

Her walk through the example:

• Flip the first two zeros (indexes 3, 4): 1 1 1 1 1 → a run of 5.
• Window 4..9 = 0 0 1 1 1 1 has two zeros → flip them → 6.
• Window 5..10 = 0 1 1 1 1 0 also has two zeros → also 6.

No window has 7 cells with only two zeros, so the answer is 6. A second LeetCode example: [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3 → 10.

2What the constraints tell us

• 1 ≤ n ≤ 10⁵ → O(n²) = 10¹⁰, beyond about 10⁸ → TLE. We'll need O(n).
• nums[i] is 0 or 1.
• 0 ≤ k ≤ n. k = 0 is allowed (no flips: this becomes problem 3). k can be as big as n (flip everything: the answer is n).

3Intuition

Walk forward from a start. 1s are always fine. Every 0 uses up one flip. As long as we've used ≤ k flips, keep going. The moment we meet the (k + 1)-th zero, this start can't go further. Its length is a candidate. Try every start, keep the best.

4Building the logic from the example

1. Start at index 0. 1 → fine. 1 → fine. 1 → fine. 0 → zero_count = 1. Is 1 > k = 2? No, keep going.
2. 0 → zero_count = 2. Still not > 2, keep going.
3. 0 at index 5 → zero_count = 3 > 2. Stop here. This start's best window is 0..4, length 5.
4. To get a length we need to remember where we started, so she keeps a left pointer at the start and moves a right pointer forward.

She sets max_len = 0 at the start: even in the worst case (for example all zeros with k = 0) the answer is 0, never negative.

5Approach steps

1. max_len = 0.
2. For each start i: zero_count = 0.
3. For each j from i: if nums[j] == 0, zero_count += 1.
4. If zero_count > k: break (this start is done).
5. Otherwise [i..j] is valid: max_len = max(max_len, j − i + 1).
6. Return max_len.

6Code (Python)

class Solution:
    def longestOnes(self, nums, k):
        n = len(nums)
        max_len = 0
        for i in range(n):
            zero_count = 0                       # fresh for every start
            for j in range(i, n):
                if nums[j] == 0:
                    zero_count += 1
                if zero_count > k:               # (k+1)-th zero: can't flip it
                    break
                max_len = max(max_len, j - i + 1)   # [i..j] is valid
        return max_len

7Code line by line

8Dry run (hand table)

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

Answer: 6 ✓. Look at rows 1, 2, 3: they stop at the same zero as row 0 and are just shorter. That's the waste Part B removes.

9Complexity & remember

• Time O(n²): on an array with no zeros (her example), j runs to the end for every i.
• Space O(1).

Part B · Better: sliding window, shrink with while

1The question again, with the new goal

Same question. Goal: stop re-walking from every start. Each pointer should cross each index only once.

2What the constraints tell us now

n up to 10⁵ → we want O(n). Values are only 0/1 and we want the longest contiguous window, where every cell inside matters → sliding window (like problem 3).

3Intuition: don't restart right; move left past a zero

In the brute force, after i = 0 stopped at the 3rd zero (index 5), we moved i to 1 and started j all over again from 1, only to stop at the same index 5 with a shorter window. Same for i = 2 and i = 3.

Her observation: the answer only changes when a zero leaves the window. Moving left past 1s just makes the window shorter while the zero count stays at 3. So:

• Keep right where it is (don't restart it).
• Move left forward until one zero has left, so the count is back to ≤ k.
• Then carry on moving right from where it was.

The two phases have names: right moving = the expansion phase; left moving because the window broke = the shrinking phase.

4Building the code from the example

1. left = 0, zero_count = 0, max_len = 0. A for loop moves right from 0 to n − 1.
2. If nums[right] == 0 → zero_count += 1.
3. If zero_count > k → shrink. She first writes this as an if with a break, then notices two problems: (a) a break there would end the whole for loop, not just the shrinking; (b) left may need to move several times (past 1, 1, 1 and then the 0). So it must be a while loop: while zero_count > k.
4. Inside the while: before moving left, look at the cell it's leaving. If nums[left] == 0, a zero is leaving, so zero_count -= 1. Then left += 1.
5. After the while, the window [left..right] is valid again. Now the length is right − left + 1 (right is a valid cell this time, so +1). Update max_len.

5Approach steps

1. left = 0, zero_count = 0, max_len = 0.
2. For right from 0 to n − 1: if nums[right] is 0 → zero_count += 1. (expand)
3. While zero_count > k: if nums[left] is 0 → zero_count −= 1; left += 1. (shrink)
4. max_len = max(max_len, right − left + 1).
5. Return max_len.

6Code (Python)

class Solution:
    def longestOnes(self, nums, k):
        left = 0
        zero_count = 0
        max_len = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                zero_count += 1                  # expand: a zero joined
            while zero_count > k:                # too many zeros: shrink
                if nums[left] == 0:
                    zero_count -= 1              # a zero is leaving
                left += 1
            max_len = max(max_len, right - left + 1)   # valid again
        return max_len

7Code line by line

8Dry run (hand table)

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

9Complexity & remember

• A while inside a for looks like O(n²), but it isn't. Her argument: right touches each index once (n moves). Left also touches each index at most once, because it never goes back and never passes right (at most n moves in total, across all the while loops together). So the total is n + n = O(2n), which is O(n).
• Space O(1).

She calls this "better, but not yet the most optimised", because in step 6 the right pointer had to wait while left walked 4 steps.

Part C · Most optimised: shift with if, return n − left

1The question again, with the new goal

Same question. Goal: exactly one pass, without right ever waiting for left. (Her interview tip below explains why this version is worth knowing.)

2What changes

Everything is the same as Part B (left, zero_count, the for loop over right, counting zeros) except two things:

1. The while becomes an if. When there are too many zeros, left moves only one step, and right carries on. Left catches up a little on each following step instead of all at once.
2. There is no max_len variable. At the end she returns n − left.

3Intuition: the window never gets smaller

In Part B the window shrank back to valid at once. Here, when it's invalid, left and right both step forward by one, so the window keeps its size and just slides. It only grows on a step where the if doesn't fire (the window is valid).

Think of it like this: the window's size is a "record" of the longest valid window found so far. We never need a smaller window, because a smaller one can't beat the record. So instead of shrinking, we slide the record-sized window forward and wait until it can grow again.

Her words for it: we aren't measuring lengths along the way, we're finding the best position for left by the time right reaches the last index.

4Building it from the example (her walk-through)

1. Right moves over 1, 1, 1: nothing happens. Then 0 → count 1, 0 → count 2 (not > 2). Window [0..4], size 5.
2. Right on index 5 (0) → count 3 > 2. In Part B, right would now wait. Here: check nums[left] (index 0, a 1, so no change to the count), left += 1 once. Window [1..5], still size 5.
3. Right moves to 6 (a 1). The count is still 3 > 2 (three zeros at 3, 4, 5 are still inside), so left moves one more step → [2..6].
4. Right to 7. Still 3 → left steps → [3..7].
5. Right to 8. Still 3 → this time nums[left] (index 3) is a 0, so the count drops to 2, then left += 1 → [4..8].
6. Right to 9 (a 1). Count 2, not > 2 → left stays. The window grows to [4..9], size 6.
7. Right to 10 (a 0) → count 3 > 2 → nums[left] (index 4) is 0 → count 2, left → 5. Window [5..10], size 6.
8. The loop ends. The window size is the answer: 6.

Why n − left?

When the for loop finishes, right has gone past the last index. In her Java loop it ends equal to n, which is out of bounds, so the window length is right − left (no +1, because index n isn't a real cell) = n − left. In Python's for loop right stops at n − 1, and (n − 1) − left + 1 is also n − left. Same answer: 11 − 5 = 6 ✓.

5Approach steps

1. left = 0, zero_count = 0, n = len(nums).
2. For right from 0 to n − 1: if nums[right] is 0 → zero_count += 1.
3. If zero_count > k: if nums[left] is 0 → zero_count −= 1; then left += 1 (just once).
4. After the loop → return n − left.

6Code (Python)

class Solution:
    def longestOnes(self, nums, k):
        n = len(nums)
        left = 0
        zero_count = 0
        for right in range(n):
            if nums[right] == 0:
                zero_count += 1
            if zero_count > k:                   # IF, not while: slide by one
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
        return n - left                          # final window size = best length

7Code line by line

8Dry run (hand table)

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

Compare with Part B at the same moment (step 6): there left jumped to 4 at once while right waited. Here left reaches 4 at step 9, moving together with right.

9Complexity & remember

• Time O(n): one loop; inside it, left moves at most one step. Right never waits.
• Space O(1).

Her submission beat about 99.86%. She also notes that Part B was already fast (O(2n) is linear too). In Big-O both are O(n). The real savings are the waiting steps and the max() call on every step.

Part D · Revision page

s = Solution()
print(s.longestOnes([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2))                          # 6
print(s.longestOnes([0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], 3))  # 10
print(s.longestOnes([1, 1, 0, 1], 0))      # 2  (k = 0 is problem 3)
print(s.longestOnes([0, 0, 0], 5))         # 3  (k >= n: whole array)
print(s.longestOnes([0, 0, 0], 0))         # 0  (no valid window)

Based on this video: Max Consecutive Ones III | Brute → Better → Optimal