Max Consecutive Ones III
Max Consecutive Ones III is a medium arrays & hashing problem solved with the sliding window · variable pattern.
The best approach, optimal (variable sliding window), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (every starting index) up.
Problem
You are given a binary array nums (every element is 0 or 1) 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 get after the flips.
Examples
Example 1
- Input
nums = [1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1], k = 2- Output
7- Why
- Flip the zeros at indices 4 and 5: indices 2..8 become seven 1s in a row. Any other pair of flips gives a shorter run.
Example 2
- Input
nums = [0, 0, 1, 0], k = 0- Output
1- Why
- No flips are allowed, so the longest run is the single 1.
Example 3
- Input
nums = [0, 0, 0], k = 3- Output
3- Why
- Every zero can be flipped, so the whole array becomes 1s.
Constraints
1 <= nums.length <= 10^5nums[i]is0or1.0 <= k <= nums.length
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (every starting index) | O(n²) | O(1) |
| Optimal (variable sliding window) | O(n) | O(1) |
1Brute force (every starting index)
O(n²)For each of n start indices the inner loop can scan the rest of the array.O(1)Only a few counters.For each start index, extend the subarray to the right while counting zeros, and stop as soon as the count would exceed k. The longest stretch found from any start is the answer.
- For each i: zeros = 0.
- For j from i: if nums[j] == 0, zeros++; if zeros > k, stop; otherwise best = max(best, j - i + 1).
- Return best.
class Solution {
public int longestOnes(int[] nums, int k) {
int n = nums.length, best = 0;
for (int i = 0; i < n; i++) {
int zeros = 0;
for (int j = i; j < n; j++) {
if (nums[j] == 0) zeros++;
if (zeros > k) break;
best = Math.max(best, j - i + 1);
}
}
return best;
}
}class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
n, best = len(nums), 0
for i in range(n):
zeros = 0
for j in range(i, n):
if nums[j] == 0:
zeros += 1
if zeros > k:
break
best = max(best, j - i + 1)
return bestclass Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size(), best = 0;
for (int i = 0; i < n; i++) {
int zeros = 0;
for (int j = i; j < n; j++) {
if (nums[j] == 0) zeros++;
if (zeros > k) break;
best = max(best, j - i + 1);
}
}
return best;
}
};function longestOnes(nums, k) {
const n = nums.length;
let best = 0;
for (let i = 0; i < n; i++) {
let zeros = 0;
for (let j = i; j < n; j++) {
if (nums[j] === 0) zeros++;
if (zeros > k) break;
best = Math.max(best, j - i + 1);
}
}
return best;
}2Optimal (variable sliding window)
O(n)Both pointers only move forward, so each index is visited at most twice.O(1)Two pointers and a counter.Keep a window [left, right] containing at most k zeros. Move right one step at a time and count zeros entering the window. When the count goes above k, advance left, decrementing the count whenever a zero leaves, until the window is valid again. Every valid window is a candidate answer.
- left = 0, zeros = 0, best = 0.
- For each right: if nums[right] == 0, zeros++.
- While zeros > k: if nums[left] == 0, zeros--; left++.
- best = max(best, right - left + 1). Return best.
class Solution {
public int longestOnes(int[] nums, int k) {
int left = 0, zeros = 0, best = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeros++;
while (zeros > k) {
if (nums[left] == 0) zeros--;
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
}class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
left = zeros = best = 0
for right, x in enumerate(nums):
if x == 0:
zeros += 1
while zeros > k:
if nums[left] == 0:
zeros -= 1
left += 1
best = max(best, right - left + 1)
return bestclass Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, zeros = 0, best = 0;
for (int right = 0; right < (int)nums.size(); right++) {
if (nums[right] == 0) zeros++;
while (zeros > k) {
if (nums[left] == 0) zeros--;
left++;
}
best = max(best, right - left + 1);
}
return best;
}
};function longestOnes(nums, k) {
let left = 0, zeros = 0, best = 0;
for (let right = 0; right < nums.length; right++) {
if (nums[right] === 0) zeros++;
while (zeros > k) {
if (nums[left] === 0) zeros--;
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}Edge cases to test
k = 0: the answer is the longest existing run of 1s, possibly 0kat least the number of zeros: the whole array- All zeros with a small k: the answer is k
- All ones: the whole array regardless of k
Hints
Hint 1
Rephrase the task: find the longest subarray that contains at most k zeros. Those zeros are the ones you flip.
Hint 2
If a window has too many zeros, any larger window with the same left end has too many as well. So grow the window on the right and shrink it on the left only when needed.
Hint 3
Keep a count of zeros inside the window [left, right]. When it exceeds k, move left forward until it is back to k, then record right - left + 1.
FAQ
What is the best time complexity for Max Consecutive Ones III?
Optimal (variable sliding window) runs in O(n) time and O(1) extra space. Both pointers only move forward, so each index is visited at most twice.
Which pattern does Max Consecutive Ones III use?
It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Repeating Character Replacement.
Is there a brute force solution for Max Consecutive Ones III?
Yes. Brute force (every starting index) takes O(n²) time and O(1) space. For each start index, extend the subarray to the right while counting zeros, and stop as soon as the count would exceed k.
Which edge cases should I test for Max Consecutive Ones III?
k = 0: the answer is the longest existing run of 1s, possibly 0; k at least the number of zeros: the whole array; All zeros with a small k: the answer is k; All ones: the whole array regardless of k.