Max Consecutive Ones III

▶

Steps

setup

Initialize variables

Initialize an empty queue to store zero indices, set left pointer to 0, and max_length to 0 before starting the iteration.

💡 Setting up these variables prepares the algorithm to track zeros and window boundaries efficiently.

Line:

zero_positions = deque()
left = 0
max_length = 0

💡 We need to track zero positions to know when to shrink the window.

expand

Expand right to index 0 (value 1)

Move right pointer to 0, include nums[0] which is 1, so no zero index added to queue.

💡 Expanding window to include more elements to find longer subarrays.

Line:

for right in range(len(nums)):
    if nums[right] == 0:
        zero_positions.append(right)

💡 Only zeros are tracked in the queue; ones just expand the window.

expand

Expand right to index 1 (value 1)

Move right pointer to 1, nums[1] is 1, no zero index added.

💡 Continuing to expand window while zero count is within limit.

Line:

if nums[right] == 0:
    zero_positions.append(right)

💡 Window can grow freely when no zeros are encountered.

expand

Expand right to index 2 (value 1)

Move right pointer to 2, nums[2] is 1, no zero index added.

💡 Window continues to expand with only ones.

Line:

if nums[right] == 0:
    zero_positions.append(right)

💡 Ones do not affect zero count or queue.

expand

Expand right to index 3 (value 0), add zero index

Right pointer moves to 3, nums[3] is 0, add index 3 to zero_positions queue.

💡 Tracking zero indices is crucial to know when to shrink window.

Line:

if nums[right] == 0:
    zero_positions.append(right)

💡 Queue now tracks one zero inside the window.

expand

Expand right to index 4 (value 0), add zero index

Right pointer moves to 4, nums[4] is 0, add index 4 to zero_positions queue.

💡 Window now contains two zeros, exactly k allowed flips.

Line:

if nums[right] == 0:
    zero_positions.append(right)

💡 Window still valid with zero count equal to k.

expand

Expand right to index 5 (value 0), add zero index and shrink window

Right pointer moves to 5, nums[5] is 0, add index 5 to zero_positions queue. Zero count now 3 > k, so shrink window by moving left to index after oldest zero (3+1=4).

💡 Shrinking window maintains at most k zeros by removing oldest zero from window.

Line:

if nums[right] == 0:
    zero_positions.append(right)
if len(zero_positions) > k:
    left = zero_positions.popleft() + 1

💡 Shrinking window discards earliest zero to keep zero count valid.

expand

Expand right to index 6 (value 1)

Right pointer moves to 6, nums[6] is 1, no zero added, window expands to include this one.

💡 Ones allow window to expand without affecting zero count.

Line:

if nums[right] == 0:
    zero_positions.append(right)

💡 Window can grow freely when no new zeros are added.

expand

Expand right to index 7 (value 1)

Right pointer moves to 7, nums[7] is 1, window expands further.

💡 Continuing to expand window with ones.

Line:

if nums[right] == 0:
    zero_positions.append(right)

💡 Window size increases without increasing zero count.

expand

Expand right to index 8 (value 1)

Right pointer moves to 8, nums[8] is 1, window expands.

💡 Window continues to grow with ones.

Line:

if nums[right] == 0:
    zero_positions.append(right)

💡 Window size increases, zero count stable.

expand

Expand right to index 9 (value 1), update max_length

Right pointer moves to 9, nums[9] is 1, window expands and max_length updates to 6.

💡 Updating max_length tracks the longest valid window found so far.

Line:

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

💡 Current window size (6) is the longest valid subarray so far.

expand

Expand right to index 10 (value 0), add zero index and shrink window

Right pointer moves to 10, nums[10] is 0, add index 10 to zero_positions. Zero count now 3 > k, shrink window by moving left to 5 (oldest zero 4 + 1).

💡 Shrinking window keeps zero count within allowed flips.

Line:

if nums[right] == 0:
    zero_positions.append(right)
if len(zero_positions) > k:
    left = zero_positions.popleft() + 1

💡 Window adjusted to maintain validity after adding new zero.

reconstruct

End of iteration, return max_length

All elements processed, return max_length which is 6 as the longest subarray length.

💡 Final answer represents the longest window with at most k zeros flipped.

Line:

return max_length

💡 Algorithm successfully found the longest valid subarray length.

from collections import deque

def longestOnes(nums, k):
    zero_positions = deque()  # STEP 1
    left = 0  # STEP 1
    max_length = 0  # STEP 1
    for right in range(len(nums)):  # STEP 2+ loop
        if nums[right] == 0:  # STEP 5,6,7,12
            zero_positions.append(right)  # STEP 5,6,7,12
        if len(zero_positions) > k:  # STEP 7,12
            left = zero_positions.popleft() + 1  # STEP 7,12
        max_length = max(max_length, right - left + 1)  # STEP 11
    return max_length  # STEP 13

if __name__ == '__main__':
    print(longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2))  # Output: 6

📊

Max Consecutive Ones III - Watch the Algorithm Execute, Step by Step

Watching each pointer move and queue update reveals how the algorithm maintains a valid window and updates the maximum length efficiently.

expand

L ▼

1

0

1

1

1

2

0

3

0

4

0

5

1

6

1

7

1

8

1

9

0

10

Metric: 0

Answer: 0

expand

L=R

1

0

1

1

1

2

0

3

0

4

0

5

1

6

1

7

1

8

1

9

0

10

Window: [1]

Metric: 0

Answer: 1

expand

L ▼

1

0

R ▼

1

1

1

2

0

3

0

4

0

5

1

6

1

7

1

8

1

9

0

10

Window: [1, 1]

Metric: 0

Answer: 2

expand

L ▼

1

0

1

1

R ▼

1

2

0

3

0

4

0

5

1

6

1

7

1

8

1

9

0

10

Window: [1, 1, 1]

Metric: 0

Answer: 3

expand

L ▼

1

0

1

1

1

2

R ▼

0

3

0

4

0

5

1

6

1

7

1

8

1

9

0

10

Window: [1, 1, 1, 0]

Metric: 1

Answer: 4

expand

L ▼

1

0

1

1

1

2

0

3

R ▼

0

4

0

5

1

6

1

7

1

8

1

9

0

10

Window: [1, 1, 1, 0, 0]

Metric: 2

Answer: 5

shrink

1

0

1

1

1

2

0

3

L ▼

0

4

R ▼

0

5

1

6

1

7

1

8

1

9

0

10

Window: [0, 0]

Metric: 2

Answer: 5

expand

1

0

1

1

1

2

0

3

L ▼

0

4

0

5

R ▼

1

6

1

7

1

8

1

9

0

10

Window: [0, 0, 1]

Metric: 2

Answer: 5

expand

1

0

1

1

1

2

0

3

L ▼

0

4

0

5

1

6

R ▼

1

7

1

8

1

9

0

10

Window: [0, 0, 1, 1]

Metric: 2

Answer: 5

expand

1

0

1

1

1

2

0

3

L ▼

0

4

0

5

1

6

1

7

R ▼

1

8

1

9

0

10

Window: [0, 0, 1, 1, 1]

Metric: 2

Answer: 5

record_answer

1

0

1

1

1

2

0

3

L ▼

0

4

0

5

1

6

1

7

1

8

R ▼

1

9

0

10

Window: [0, 0, 1, 1, 1, 1]

Metric: 2

Answer: 6

shrink

1

0

1

1

1

2

0

3

0

4

L ▼

0

5

1

6

1

7

1

8

1

9

R ▼

0

10

Window: [0, 1, 1, 1, 1, 0]

Metric: 2

Answer: 6

record_answer

1

0

1

1

1

2

0

3

0

4

L ▼

0

5

1

6

1

7

1

8

1

9

R ▼

0

10

Window: [0, 1, 1, 1, 1, 0]

Metric: 2

Answer: 6

Key Takeaways

✓ Tracking zero indices in a queue allows efficient window shrinking when zero count exceeds k.

Without visualizing the queue, it's hard to see how the algorithm knows which zero to remove.

✓ The window expands greedily until invalid, then shrinks just enough to restore validity.

This dynamic resizing is key to achieving linear time complexity.

✓ Updating max_length after each valid window ensures the longest subarray is found without extra passes.

This incremental update avoids recomputing window sizes repeatedly.

Practice

1. Consider the following Python code implementing the optimal sliding window approach for the character replacement problem. What is the returned value when the input is s = "AABA" and k = 1?

easy

A. 4

B. 3

C. 2

D. 1

Solution

1. Step 1: Trace window expansion and frequency updates

   Index 0: freq[A]=1, max_count=1, window=[0,0], max_len=1 Index 1: freq[A]=2, max_count=2, window=[0,1], max_len=2 Index 2: freq[B]=1, max_count=2, window=[0,2], window size=3, replacements needed=1 ≤ k=1, max_len=3 Index 3: freq[A]=3, max_count=3, window=[0,3], window size=4, replacements needed=1 ≤ k=1, max_len=4

2. Step 2: Check while condition and final max_len

   At index 3, window size 4 with max_count 3 means 1 replacement needed, which is allowed. So max_len updates to 4. The function returns 4.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Window expands fully with one replacement allowed [OK]

Hint: Max length includes full string if replacements ≤ k [OK]

Common Mistakes:

• Off-by-one error in window size calculation
• Not updating max_count correctly
• Misunderstanding when to shrink window

2. Consider the following code snippet implementing the optimal sliding window approach for longest substring with at most k distinct characters. What is the returned value when calling length_of_longest_substring_k_distinct('aabbcc', 2)?

easy

A. 6

B. 3

C. 2

D. 4

Solution

1. Step 1: Trace window expansion and last_seen updates

   For 'aabbcc' with k=2, the longest substring with at most 2 distinct chars is 'aabb' or 'bbcc', length 4.

2. Step 2: Confirm max_length calculation

   max_length updates to 4 when window covers 'aabb' or 'bbcc'. The function returns 4.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Longest valid substring length is 4 [OK]

Hint: Longest substring with 2 distinct chars in 'aabbcc' is length 4 [OK]

Common Mistakes:

• Off-by-one errors counting substring length
• Confusing distinct character count when shrinking window

3. Consider the following code snippet implementing the optimal sliding window approach to check if s2 contains a permutation of s1. Given s1 = "ab" and s2 = "eidbaooo", what is the return value of the function?

easy

A. True

B. Raises an IndexError

C. False

D. Returns None

Solution

1. Step 1: Trace window expansion and counts

   For s1 = "ab", count array has counts for 'a' and 'b'. Sliding window moves over s2 = "eidbaooo". When window covers substring "ba" starting at index 3, window_count matches count, so formed == required.

2. Step 2: Confirm return value

   At this point, function returns True because a permutation of s1 is found in s2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Substring "ba" is a permutation of "ab" [OK]

Hint: Check substring "ba" matches "ab" permutation [OK]

Common Mistakes:

• Off-by-one errors in window size
• Forgetting to return True when formed == required

4. What is the time complexity of the optimal sliding window solution for the fruits problem, given an input array of length n? Assume fruit types are arbitrary integers but the number of distinct fruit types in the window is limited to two.

medium

A. O(n) because each element is visited at most twice by the two pointers

B. O(n log n) due to maintaining the hash map keys in sorted order

C. O(n²) because the inner while loop can run multiple times per outer iteration

D. O(n * k) where k is the number of distinct fruit types in the array

Solution

1. Step 1: Analyze outer and inner loops

   The right pointer moves from 0 to n-1 once; the left pointer only moves forward when shrinking window.

2. Step 2: Each element is added and removed at most once

   Thus total operations are proportional to 2n, which is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window with hashmap is linear time [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Assuming nested loops multiply to n²
• Thinking hashmap operations add log n
• Confusing distinct fruit count with input size

5. The following code attempts to implement the optimal sliding window approach to check if s2 contains a permutation of s1. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line checking if window_count[idx] == count[idx] to increment formed

B. Line computing required as sum of positive counts

C. Line decrementing window_count[left_idx] before adjusting formed

D. Line checking if len_s1 > len_s2 at start

Solution

1. Step 1: Identify bug in window shrinking logic

   The code decrements window_count[left_idx] before checking if it equals count[left_idx]. This causes incorrect formed count updates because the check should happen before decrement.

2. Step 2: Correct order of operations

   To fix, check if window_count[left_idx] == count[left_idx] before decrementing window_count[left_idx], then decrement and adjust formed accordingly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Formed count must reflect window state before decrement [OK]

Hint: Check order of decrement and formed adjustment in window shrink [OK]

Common Mistakes:

• Adjusting formed after decrementing counts
• Miscounting required matches