Max Consecutive Ones III
Medium · Arrays & Hashing · Array · Binary Search · Sliding Window · Prefix Sum
Problem
You are given a binary array nums and an integer k. You may flip at most k zeros into ones.
Return the length of the longest contiguous run of 1s you can obtain.
Examples
Input: nums = [1,1,0,1,1,0,0,1], k = 1 Output: 5
Flipping the zero at index 2 joins two pairs of ones into a run of 5.
Input: nums = [1,0,1,1,1,0], k = 0 Output: 3
No flips are allowed, so the longest existing run of ones, 3, is the answer.
Input: nums = [0,0,0], k = 2 Output: 2
Two of the three zeros can be flipped.
Constraints
- 1 <= len(nums) <= 10^5
- nums[i] is either 0 or 1
- 0 <= k <= len(nums)
Approaches
- Baseline: every start, extend until a flip too many — time O(n²), space O(1)
Follow-up
What if the array arrives as a stream too long to keep? The window needs the positions of the zeros inside it, not the whole array: keep a queue of the last k + 1 zero positions, and the window start is just after the oldest one once there are more than k.
Related problems
Start free on Cariara · Coding problems · System design studio
