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

Max Consecutive Ones

The second sliding window question in the sheet, and the first one where the window has no fixed size. The teacher starts with a two-loop brute force, shows on an all-ones array how much of its work is wasted, picks the pattern by ruling the others out, and then writes a one-pass counter. While submitting she also finds a classic bug: the last run of ones is never checked if the array doesn't end in a 0, and she fixes it on screen.

Why it matters: this is the simplest variable-size, longest-window problem. Its "when the window breaks, jump the left end straight past the bad cell" idea, and its "check once more after the loop" lesson, come back in Max Consecutive Ones III and many string problems.

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: a run from every start
• Part B · Optimal: one pass with a running count (sliding window)
• Part C · Revision page

Part 0 · Before starting

Subarray = window

A subarray is a contiguous piece of an array (start, end, everything in between, nothing skipped). We call it a window and write it as [left..right], both ends included. Length = right − left + 1. "Consecutive ones" just means a window that contains only 1s.

The brute force tries every start and walks an end pointer forward: about n² steps, and windows that overlap get counted again and again. A sliding window walks right forward once, and moves left forward only when it has to. Neither pointer ever goes back, so the total work is O(n).

• Expand: right moves one step, a cell joins the window.
• Shrink: left moves forward, cells leave the window. Cells that leave never come back (drawn grey below).

Fixed vs variable windows

Other shapes later in the notebook: shortest valid window (record while shrinking), count of valid windows (count += right − left + 1), and "exactly K = atMost(K) − atMost(K − 1)". Variable windows need a one-way condition: once a window is bad, growing it can't make it good again. Here that's true: once a 0 is inside, adding more cells never removes it. (For sums, the same idea fails with negative numbers.) Problem 1 covers all of these.

The 4 array patterns the teacher checks

Part A · Brute force: a run from every start

LeetCode 485

1The question in simple words

You get a binary array nums (every value is 0 or 1). Return the length of the longest stretch of 1s in a row.

Count the first run: 2. The 0 can't be included, so after it we start counting again: 1, 2, 3. The bigger run is 3. Another LeetCode example: [1, 0, 1, 1, 0, 1] → 2.

2What the constraints tell us

• 1 ≤ n ≤ 10⁵. O(n²) = 10¹⁰ steps, far beyond about 10⁸ → TLE. We'll need O(n). She still writes the brute force first.
• nums[i] is 0 or 1. No negatives, no big numbers. This will rule out Kadane's later.
• n ≥ 1, so the array is never empty (but the answer can be 0 if it's all zeros).

3Intuition

Stand at each index i. If it's a 1, walk forward with a second pointer j while you keep seeing 1s. When j hits a 0, the run that started at i is over. Its length is the answer for this start. Do this for every i and keep the largest.

4Building the logic from her examples

Example: [1, 1, 1, 0, 1, 1, 1, 1]

1. i = 0. j starts at i: 1 ✓, 1 ✓, 1 ✓, then index 3 is 0 → stop. j = 3.
2. Length? Indexes 0, 1, 2 are the run, that's 3. And j − i = 3 − 0 = 3.
3. i = 1 → j stops at 3 again → length 2. i = 2 → length 1. i = 3 is itself a 0 → j doesn't move → length 0.
4. i = 4 → j walks 4, 5, 6, 7 and then runs off the end (j = 8) → length 4.

Her all-ones example: where the time goes

Take [1, 1, 1, 1, 1]. From i = 0, j walks all 5 cells → length 5. From i = 1, j walks 4 cells → 4. From i = 2 → 3… Every start walks to the end. That's 5 + 4 + 3 + 2 + 1 steps, about n²/2.

And it's pointless: from i = 0 we already got the longest run (5); every later start in the same run is guaranteed to be shorter, because it stops at the same place but starts later. This waste is what Part B removes.

Her code, and a bug in it

Her brute force: for every i, a loop for j; when nums[j] == 0, compute the length j − i, update the max, and break out of the j loop.

5Approach steps

1. best = 0.
2. For each start i: put j at i.
3. While j is inside the array and nums[j] == 1: move j forward.
4. j is now on a 0 or at n. The run is i..j−1, length j − i. Update best.
5. Return best.

6Code (Python)

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        n = len(nums)
        best = 0
        for i in range(n):
            j = i                                # start the run at i
            while j < n and nums[j] == 1:        # stop at a 0 OR at the end
                j += 1
            best = max(best, j - i)              # j is not part of the run
        return best

7Code line by line

8Dry run (hand table)

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

Answer: 4 ✓. With the break-only version, the rows for i = 4..7 would record nothing and the answer would be 3 ✗.

9Complexity & remember

• Time O(n²) in the worst case. Her point: "but I break at a 0!" doesn't help when there are no 0s. On all ones, every i walks to the end. With n = 10⁵ that's about 10¹⁰/2 steps → TLE.
• Space O(1).

Part B · Optimal: one pass with a running count (sliding window)

1The question again, with the new goal

Same question, but now in one pass: O(n).

2Choosing the pattern

• ✗ Two pointers: for when only two positions matter. Here every cell inside the run matters (each must be a 1), and a 0 ends the subarray and starts a new one.
• ✗ Prefix sum: for contiguous sums. We don't need any sum, just a length.
• ✗ Kadane's: for sums with negative numbers. The values are only 0 and 1.
• ✓ Sliding window: a contiguous window where every cell inside matters, and we want the longest one.

3Intuition: don't restart inside a run

From Part A: if i = 0 runs until the 0 at index 3, then starting at i = 1 or 2 hits the same 0 and is just shorter. So the best length for this run already came from its leftmost start.

So when we hit a 0, there's no point moving the start forward one step at a time. Jump the start straight to the cell after the 0, and start a fresh run there. In window terms: the window is the current run of 1s; a 0 empties it, and left jumps to right + 1.

And since we only need the length of the current run, we don't even need a left pointer: a counter count does it. A 1 → count += 1. A 0 → the run is over: save it in the max and reset count = 0.

4Building the logic, the way she writes it

1. Variables: max_count = 0 (the answer), count = 0 (the current run's length).
2. She first writes a while loop with j: if nums[j] == 1, then j += 1 and count += 1. Else (a 0): update max_count = max(max_count, count), reset count = 0, and j += 1.
3. She notices j += 1 is in both branches, so it can move out of the if/else. And a pointer that moves one step every time, no matter what, is just a for loop. So she switches to a for loop. Same logic.

The bug she finds while dry-running (her most important point)

Take [1, 1, 1, 0, 1, 1, 1, 1]. The first run (3) is saved when the 0 arrives. Then count goes 1, 2, 3, 4 on the last run... and the loop ends. The else branch only runs on a 0, and no 0 comes after the last run. So 4 is never compared with max_count. Returning max_count gives 3 ✗.

(She first types return count, corrects it to return max_count, and then spots this case.) The fix: compare one last time before returning: return max(max_count, count).

5Approach steps

1. max_count = 0, count = 0.
2. For each value x in nums: if x is 1 → count += 1.
3. Else (x is 0) → max_count = max(max_count, count), then count = 0.
4. After the loop → return max(max_count, count) (the last run may never have been saved).

6Code (Python)

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        max_count = 0
        count = 0                                # length of the current run of 1s
        for j in range(len(nums)):
            if nums[j] == 1:
                count += 1                       # the run grows
            else:
                max_count = max(max_count, count)   # a 0 ends the run: save it
                count = 0                        # start fresh after the 0
        return max(max_count, count)             # the last run was never saved

class Solution:
    def findMaxConsecutiveOnes(self, nums):
        left = 0
        best = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                left = right + 1                 # window can't hold a 0: jump past it
            else:
                best = max(best, right - left + 1)
        return best

7Code line by line

8Dry run (hand table)

nums = [1, 1, 1, 0, 1, 1, 1, 1]. In her code, count = the window's length and the window is [left..right].

The LeetCode example [1, 1, 0, 1, 1, 1] has the same trap: the longest run (3) is at the end, so without the final check you'd return 2.

9Complexity & remember

• Time O(n): the loop runs n times, with O(1) work inside. All the useless re-counting from Part A is gone.
• Space O(1).

Her Java submission beat about 98%.

Part C · Revision page

s = Solution()
print(s.findMaxConsecutiveOnes([1, 1, 0, 1, 1, 1]))         # 3
print(s.findMaxConsecutiveOnes([1, 0, 1, 1, 0, 1]))         # 2
print(s.findMaxConsecutiveOnes([1, 1, 1, 0, 1, 1, 1, 1]))   # 4 (last run is the longest)
print(s.findMaxConsecutiveOnes([1, 1, 1, 1, 1]))            # 5 (no zeros at all)
print(s.findMaxConsecutiveOnes([0, 0, 0]))                  # 0 (no ones)

Based on this video: Max Consecutive Ones | Sliding Window