Practice › Sliding Window
Max Consecutive Ones III
Medium · Sliding Window · Asked at Amazon, Meta, Google, Microsoft
The array contains only 0s and 1s. You may flip at most k zeros to ones. Print the length of the longest run of consecutive ones you can get.
Input
First line: n k. Second line: n values (0 or 1).
Output
The maximum length.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ k ≤ n
Longest window containing at most k zeros: grow on the right, shrink from the left while there are more than k zeros.
Example 1
Input
11 2 1 1 1 0 0 0 1 1 1 1 0
Output
6
Example 2
Input
5 0 0 0 1 1 0
Output
2
Hints
- Flipping at most k zeros = finding the longest window that contains at most k zeros.
- Move the right end one step at a time; whenever the window has more than k zeros, move the left end forward.
Approach
Maintain a window [l, r] and the number of zeros inside it. Add a[r]; while zeros > k, remove a[l] and advance l. Every window you end up with is valid, so record its length. Each index enters and leaves the window once.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto &x : a) cin >> x;
int l = 0, zeros = 0, best = 0;
for (int r = 0; r < n; r++) {
zeros += a[r] == 0;
while (zeros > k) zeros -= a[l++] == 0;
best = max(best, r - l + 1);
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, k, a = data[0], data[1], data[2:]
l = zeros = best = 0
for r in range(n):
zeros += a[r] == 0
while zeros > k:
zeros -= a[l] == 0
l += 1
best = max(best, r - l + 1)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), k = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
int l = 0, zeros = 0, best = 0;
for (int r = 0; r < n; r++) {
if (a[r] == 0) zeros++;
while (zeros > k) if (a[l++] == 0) zeros--;
best = Math.max(best, r - l + 1);
}
System.out.println(best);
}
}Solve Max Consecutive Ones III online · All practice problems