Skip to main content

18. Max Consecutive Ones III

mediumAsked at Rappi

Find the longest substring of ones if you can flip at most k zeros — Rappi frames this as finding the longest continuous on-time delivery streak per courier when you can forgive up to k delays.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 zeros to ones.

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= k <= nums.length

Examples

Example 1

Input
nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output
6

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

Approaches

1. Try every window

For each (l,r), count zeros in nums[l..r] and accept if <= k.

Time
O(n^2)
Space
O(1)
let best = 0;
for (let l=0;l<nums.length;l++) {
  let z = 0;
  for (let r=l;r<nums.length;r++) {
    if (nums[r]===0) z++;
    if (z<=k) best = Math.max(best, r-l+1);
  }
}
return best;

Tradeoff:

2. Sliding window with zero budget

Expand right; if zeros in window exceed k, advance left. Window size is the answer at every step.

Time
O(n)
Space
O(1)
function longestOnes(nums, k) {
  let l = 0, z = 0, best = 0;
  for (let r = 0; r < nums.length; r++) {
    if (nums[r] === 0) z++;
    while (z > k) { if (nums[l] === 0) z--; l++; }
    best = Math.max(best, r - l + 1);
  }
  return best;
}

Tradeoff:

Rappi-specific tips

Rappi expects the sliding-window pattern verbatim — it's the same shape their on-time streak calculator uses across courier shift data.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Max Consecutive Ones III and other Rappi interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →