Max Consecutive Ones III

📋

Problem

Imagine you are streaming a binary signal and want to find the longest segment where you can flip at most K zeros to ones to maintain a strong signal.

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 to 1's. Input: nums (list of 0s and 1s), k (integer). Output: integer representing the length of the longest subarray with at most k zeros.

1 ≤ nums.length ≤ 10^5nums[i] is either 0 or 10 ≤ k ≤ nums.length

Edge cases: All elements are 1 → output is length of arrayAll elements are 0 and k = 0 → output is 0k is equal to array length → output is length of array

</>

IDE

def longestOnes(nums: list[int], k: int) -> int:public int longestOnes(int[] nums, int k)int longestOnes(vector<int>& nums, int k)function longestOnes(nums, k)

def longestOnes(nums, k):
    # Write your solution here
    pass

class Solution {
    public int longestOnes(int[] nums, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int longestOnes(vector<int>& nums, int k) {
    // Write your solution here
    return 0;
}

function longestOnes(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 5Greedy approach flips first k zeros only, missing longer windows later.✅ Use sliding window with zero count and move left pointer to maintain at most k zeros.

Wrong: 7Allowing more than k zeros flipped by not shrinking window properly.✅ Track zeros count and shrink window from left when zeros exceed k.

Wrong: 4Off-by-one error in window length calculation or pointer updates.✅ Calculate window length as end - start + 1 and update zero count correctly.

Wrong: Runtime Error or Wrong AnswerNot handling empty input or single element arrays properly.✅ Add base cases for empty array and single element arrays.

Wrong: TimeoutUsing brute force O(n^2) approach instead of O(n) sliding window.✅ Implement sliding window with two pointers and zero count for O(n) complexity.

✓

Test Cases

Focus on handling base cases like empty arrays and single elements correctly.

Think about tricky cases where greedy approaches fail or off-by-one errors occur.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,1,1,0,0,0,1,1,1,1,0],"k":2}

Expected6

⏱ Performance - must finish in 2000ms

Flip two zeros at positions 5 and 10 to get the longest consecutive ones subarray of length 7.

💡 Consider using a sliding window to track zeros within the window.

💡 Maintain a count of zeros and adjust the window size when zeros exceed k.

💡 Expand the window while zeros count <= k, shrink from left when zeros > k.

Why it failed: Incorrect output likely due to not properly shrinking the window when zeros exceed k. Fix by moving left pointer until zeros count <= k.

✓ Correctly handles sliding window with zero flips.

t1_02basic

Input{"nums":[0,1,1,0,1,1,0,1],"k":1}

Expected5

⏱ Performance - must finish in 2000ms

Flip one zero at position 3 or 6 to get longest consecutive ones subarray of length 4.

💡 Try to find the longest window with at most k zeros.

💡 Use two pointers and count zeros inside the window.

💡 When zeros exceed k, move left pointer until zeros count is k again.

Why it failed: Fails if zeros count not tracked correctly or window not shrunk properly when zeros exceed k. Fix by updating zero count and left pointer accordingly.

✓ Correctly finds longest subarray with at most k zero flips.

t2_01edge

Input{"nums":[],"k":0}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no elements, so longest consecutive ones is 0.

💡 Check how your code handles empty input arrays.

💡 Make sure to handle n=0 without errors or incorrect results.

💡 Return 0 immediately if array is empty.

Why it failed: Fails on empty input by not returning 0 or causing error. Fix by adding base case for empty array.

✓ Handles empty input correctly.

t2_02edge

Input{"nums":[1],"k":0}

Expected1

⏱ Performance - must finish in 2000ms

Single element 1 with k=0 means longest consecutive ones is 1.

💡 Test single element arrays to ensure correct base case.

💡 Check if code correctly counts single 1 without flipping.

💡 Return 1 if single element is 1 and k >= 0.

Why it failed: Fails single element case by not returning 1 when element is 1. Fix by handling single element base case correctly.

✓ Correctly handles single element arrays.

t2_03edge

Input{"nums":[0,0,0,0],"k":4}

Expected4

⏱ Performance - must finish in 2000ms

k equals array length, so all zeros can be flipped to ones, longest subarray is entire array length 4.

💡 Consider cases where k equals or exceeds number of zeros.

💡 Your window can cover entire array if zeros <= k.

💡 Return length of array if zeros count <= k.

Why it failed: Fails when k equals array length by not flipping all zeros. Fix by allowing window to expand fully when zeros <= k.

✓ Correctly handles full flip when k equals array length.

t3_01corner

Input{"nums":[1,0,1,0,1,0,1,0,1],"k":2}

Expected5

⏱ Performance - must finish in 2000ms

Greedy approach fails here; best window flips two zeros to get max length 5.

💡 Beware of greedy approaches that flip zeros from left only.

💡 Use sliding window to dynamically adjust window size based on zero count.

💡 Track zeros count and move left pointer to maintain at most k zeros.

Why it failed: Fails greedy trap by flipping first k zeros only, missing longer windows. Fix by using sliding window with zero count and adjusting left pointer.

✓ Correctly handles greedy trap with sliding window.

t3_02corner

Input{"nums":[0,0,1,1,0,0,1,1,1,0],"k":3}

Expected8

⏱ Performance - must finish in 2000ms

Confuses 0/1 knapsack with unbounded; must count zeros in window, not flip unlimited zeros.

💡 Do not treat zeros flips as unlimited; limit to k flips.

💡 Sliding window must maintain zero count <= k.

💡 Shrink window from left when zeros exceed k.

Why it failed: Fails 0/1 constraint by allowing more than k zeros flipped. Fix by counting zeros and shrinking window when zeros > k.

✓ Correctly enforces zero flip limit.

t3_03corner

Input{"nums":[1,1,0,1,1,0,1,1,1],"k":1}

Expected6

⏱ Performance - must finish in 2000ms

Off-by-one errors cause incorrect window size; correct max length is 6.

💡 Check window length calculation carefully (end - start + 1).

💡 Ensure pointers update correctly when shrinking window.

💡 Verify zero count updates when moving left pointer.

Why it failed: Off-by-one error in window length calculation or pointer updates. Fix by using correct window length formula and updating zero count properly.

✓ Correctly calculates window length and updates pointers.

t4_01performance

Input{"nums":[0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,0,1,1],"k":25}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) sliding window solution must complete within 2 seconds.

💡 Use O(n) sliding window approach to handle large input efficiently.

💡 Avoid nested loops or brute force O(n^2) solutions.

💡 Maintain zero count and adjust window pointers in linear time.

Why it failed: TLE due to using O(n^2) brute force approach. Fix by implementing O(n) sliding window algorithm.

✓ Efficient O(n) solution confirmed by passing performance test.

Practice

1. Given the following code snippet, what is the output when calling numSubarraysWithSum([1,0,1], 2)?

easy

A. 2

B. 4

C. 1

D. 3

Solution

1. Step 1: Trace atMost(2)

   Right=0: current_sum=1 ≤2, count=1; Right=1: current_sum=1 ≤2, count=1+2=3; Right=2: current_sum=2 ≤2, count=3+3=6

2. Step 2: Trace atMost(1)

   Right=0: current_sum=1 ≤1, count=1; Right=1: current_sum=1 ≤1, count=1+2=3; Right=2: current_sum=2 >1, shrink window: current_sum=1, left=1, count=3+2=5

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   numSubarraysWithSum = 6 - 5 = 1 [BUG]

Hint: Subtract atMost(goal-1) from atMost(goal) to get exact count [OK]

Common Mistakes:

• Miscounting subarrays when shrinking window
• Off-by-one errors in count increments
• Confusing atMost(goal) with exact count

2. 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

3. Consider the following buggy code for maxSatisfied. Which line contains the subtle bug that causes incorrect results on some inputs?

def maxSatisfied(customers, grumpy, X):
    n = len(customers)
    base_satisfied = 0
    for i in range(n):
        if grumpy[i] == 0:
            base_satisfied += customers[i]
    window_sum = 0
    for i in range(X):
        if grumpy[i] == 1:
            window_sum += customers[i]
    max_extra = window_sum
    for i in range(X, n):
        if grumpy[i] == 1:
            window_sum += customers[i]
        if grumpy[i - X] == 0:
            window_sum -= customers[i - X]
        if window_sum > max_extra:
            max_extra = window_sum
    return base_satisfied + max_extra

medium

A. Line checking if grumpy[i] == 1 before adding customers[i]

B. Line initializing base_satisfied with customers where grumpy[i] == 0

C. Line checking if grumpy[i - X] == 0 before subtracting customers[i - X]

D. Line updating max_extra when window_sum > max_extra

Solution

1. Step 1: Identify subtraction condition

   The code subtracts customers[i - X] only if grumpy[i - X] == 0, but it should subtract only if grumpy[i - X] == 1 because only grumpy customers were added.

2. Step 2: Consequence of bug

   This causes incorrect window sums, as some grumpy customers are never subtracted, inflating window_sum.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Subtraction condition must match addition condition [OK]

Hint: Check symmetry of add and subtract conditions [OK]

Common Mistakes:

• Confusing grumpy check in subtraction
• Forgetting to subtract outgoing element
• Mixing base satisfaction with window sums

4. What is the time complexity of the optimized sliding window algorithm that uses a hash map to track the last seen indices of characters for finding the longest substring without repeating characters?

medium

A. O(n) because each character is visited at most twice by the right and left pointers

B. O(n^2) because each character may cause the left pointer to move multiple times

C. O(n log n) due to hash map operations on each character

D. O(n * m) where m is the size of the character set

Solution

1. Step 1: Analyze pointer movements

   Right pointer moves forward once per character. Left pointer only moves forward when duplicates are found, never backward. Each character is visited at most twice.

2. Step 2: Consider hash map operations

   Hash map lookups and updates are O(1) average. Thus total time is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window with hash map -> linear time [OK]

Hint: Each character visited max twice -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing hash map average with worst-case

5. Suppose the problem is modified so that the array can contain negative integers and zeros, and you want to count subarrays with exactly k odd numbers. Which modification to the sliding window approach is necessary to handle this variant correctly?

hard

A. Modify the odd number check to use absolute value: nums[right] % 2 != 0

B. No modification needed; the existing sliding window works for any integers

C. Use prefix sums of odd counts instead of sliding window to handle negatives

D. Sliding window must reset when encountering negative numbers to avoid incorrect counts

Solution

1. Step 1: Identify odd number condition with negatives

   Negative odd numbers still have odd absolute value, so check must consider absolute value.

2. Step 2: Modify odd check

   Change condition to nums[right] % 2 != 0 or abs(nums[right]) % 2 == 1 to correctly count odd numbers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Oddness depends on absolute value, not sign [OK]

Hint: Oddness depends on absolute value, not sign [OK]

Common Mistakes:

• Assuming negative numbers are never odd
• Resetting sliding window unnecessarily
• Switching to prefix sums without need