Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Flipping at most k zeros = finding the longest window that contains at most k zeros.
  2. 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