1004. Max Consecutive Ones III
Asked at Meta, DE Shaw
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
Array
Companies
2
Problem
You get a binary array nums (only 0s and 1s) and an integer k. You may change at most k of the 0s into 1s. After doing that, some run of 1s becomes longer.
Return the length of the longest block of consecutive 1s you can create. The block must be a contiguous subarray — the elements must sit next to each other. You do not have to use all k flips; using fewer is allowed.
Think of it this way: find the longest window that contains at most k zeros. Every zero inside that window can be flipped, so the whole window becomes 1s.
Flip at most k zeros, then measure the longest run
Constraints
- ●
1 <= nums.length <= 10^5 - ●
nums[i] is either 0 or 1 - ●
0 <= k <= nums.length
Examples
nums = [1,1,1,0,0,0,1,1,1,1,0], k = 26nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 310Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
| DE Shaw | Medium | View all DE Shaw questions → |
How to Think About It
Brute force: for each starting index, try flipping up to k zeros and count the longest run.
Use a sliding window that tracks the count of zeros in the current window.
Expand the right pointer and shrink the left pointer when zeros exceed k.
Binary search on prefix sums: for each index i, find the farthest j where sum[j] - sum[i] <= k.
Optimal O(n) sliding window with O(1) space by maintaining a zero counter.
Optimal Approach
Use a sliding window approach. Maintain left and right pointers. Expand right and count zeros encountered. When zeros exceed k, move left pointer forward while decrementing zeros. Track the maximum window size at each step. This runs in O(n) time with O(1) space. The window [left, right] always contains at most k zeros, and the answer is the maximum window size.
Sliding window with a zero counter
What Trips People Up in Real Interviews
Clarify if the array contains only 0s and 1s.
Ask whether k zeros can be flipped or exactly k must be flipped.
Mention that the sliding window approach is preferred over binary search in interviews.
Edge cases: k equals array length (return n), k is 0 (count existing runs), no zeros.
Walk through an example like [1,1,0,0,1,1,1,0,1] with k=2 step by step.
Solution Code
O(n) timedef longestOnes(nums, k):
left = 0
zeros = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zeros += 1
while zeros > k:
if nums[left] == 0:
zeros -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_lenFrequently Asked Questions
What is the Max Consecutive Ones III 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 0's. This problem tests your ability to optimize a sliding window using prefix sums or binary search on the number of flips.
How do you solve Max Consecutive Ones III?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Max Consecutive Ones III?
Max Consecutive Ones III is asked at Meta, DE Shaw. It is a medium difficulty problem.
What are common mistakes on Max Consecutive Ones III?
- Clarify if the array contains only 0s and 1s.
- Ask whether k zeros can be flipped or exactly k must be flipped.
- Mention that the sliding window approach is preferred over binary search in interviews.
- Edge cases: k equals array length (return n), k is 0 (count existing runs), no zeros.
- Walk through an example like [1,1,0,0,1,1,1,0,1] with k=2 step by step.