Find the maximum sequence of continuous 1’s formed by replacing at-most `k` zeros by ones

Given a binary array, find the maximum sequence of continuous 1’s that can be formed by replacing at most k zeros by ones.

For example, consider the following binary array A:

Input: A[] = { 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0 }

For k = 0,
The length of the longest sequence is 4 (from index 6 to 9)

For k = 1,
The length of the longest sequence is 7 (from index 3 to 9)

For k = 2,
The length of the longest sequence is 10 (from index 0 to 9)

For k = 3,
The length of the longest sequence is 11 (from index 0 to 10)

Practice this problem

We can solve this problem by using the sliding window technique. The idea is to maintain a window containing at most k zeros at any point. Add elements to the window from the right until it becomes unstable. The window becomes unstable if the total number of zeros in it becomes more than k. If the window becomes unstable, remove elements from its left till it becomes stable again (by removing leftmost zero). If the window is stable and the current window length is more than the maximum window found so far, set the maximum window size to the current window size.

The algorithm can be implemented as follows in C, Java, and Python:

C

#include <stdio.h>

// Function to find the maximum sequence of continuous 1's by replacing

// at most `k` zeros by 1 using sliding window technique

void findLongestSequence(int arr[], int n, int k)

{

int left = 0; // represents the current window's starting index

int count = 0; // stores the total number of zeros in the current window

int window = 0; // stores the maximum number of continuous 1's found

// so far (including `k` zeros)

int leftIndex = 0; // stores the left index of maximum window found so far

// maintain a window `[left…right]` containing at most `k` zeros

for (int right = 0; right < n; right++)

{

// if the current element is 0, increase the count of zeros in the

// current window by 1

if (arr[right] == 0) {

count++;

}

// the window becomes unstable if the total number of zeros in it becomes

// more than `k`

while (count > k)

{

// if we have found zero, decrement the number of zeros in the

// current window by 1

if (arr[left] == 0) {

count--;

}

// remove elements from the window's left side till the window

// becomes stable again

left++;

}

// when we reach here, window `[left…right]` contains at most

// `k` zeros, and we update max window size and leftmost index

// of the window

if (right - left + 1 > window)

{

window = right - left + 1;

leftIndex = left;

}

// no sequence found

if (window == 0) {

return;

}

// print the maximum sequence of continuous 1's

printf("The longest sequence has length %d from index %d to %d",

window, leftIndex, (leftIndex + window - 1));

}

int main()

{

int arr[] = { 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0 };

int k = 2;

int n = sizeof(arr) / sizeof(arr[0]);

findLongestSequence(arr, n, k);

return 0;

}

Download Run Code

Output:

The longest sequence has length 10 from index 0 to 9

Java

class Main

{

// Function to find the maximum sequence of continuous 1's by replacing

// at most `k` zeros by 1 using sliding window technique

public static void findLongestSequence(int[] A, int k)

{

int left = 0; // represents the current window's starting index

int count = 0; // stores the total number of zeros in the current window

int window = 0; // stores the maximum number of continuous 1's found

// so far (including `k` zeros)

// store left index of max window found so far

int leftIndex = 0;

// maintain a window `[left…right]` containing at most `k` zeros

for (int right = 0; right < A.length; right++)

{

// if the current element is 0, increase the count of zeros in the

// current window by 1

if (A[right] == 0) {

count++;

}

// the window becomes unstable if the total number of zeros in it becomes

// more than `k`

while (count > k)

{

// if we have found zero, decrement the number of zeros in the

// current window by 1

if (A[left] == 0) {

count--;

}

// remove elements from the window's left side till the window

// becomes stable again

left++;

}

// when we reach here, window `[left…right]` contains at most

// `k` zeros, and we update max window size and leftmost index

// of the window

if (right - left + 1 > window)

{

window = right - left + 1;

leftIndex = left;

}

// no sequence found

if (window == 0) {

return;

}

// print the maximum sequence of continuous 1's

System.out.println("The longest sequence has length " + window +

" from index " + leftIndex + " to " + (leftIndex + window - 1));

}

public static void main(String[] args)

{

int[] A = { 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0 };

int k = 2;

findLongestSequence(A, k);

}

Download Run Code

Output:

The longest sequence has length 10 from index 0 to 9

Python

# Function to find the maximum sequence of continuous 1's by replacing

# at most `k` zeros by 1 using sliding window technique

def findLongestSequence(A, k):

left = 0 # represents the current window's starting index

count = 0 # stores the total number of zeros in the current window

window = 0 # stores the maximum number of continuous 1's found

# so far (including `k` zeros)

leftIndex = 0 # stores the left index of maximum window found so far

# maintain a window `[left…right]` containing at most `k` zeros

for right in range(len(A)):

# if the current element is 0, increase the count of zeros in the

# current window by 1

if A[right] == 0:

count = count + 1

# the window becomes unstable if the total number of zeros in it becomes

# more than `k`

while count > k:

# if we have found zero, decrement the number of zeros in the

# current window by 1

if A[left] == 0:

count = count - 1

# remove elements from the window's left side till the window

# becomes stable again

left = left + 1

# when we reach here, window `[left…right]` contains at most

# `k` zeros, and we update max window size and leftmost index

# of the window

if right - left + 1 > window:

window = right - left + 1

leftIndex = left

# no sequence found

if window == 0:

return

# print the maximum sequence of continuous 1's

print("The longest sequence has length", window, "from index",

leftIndex, "to", (leftIndex + window - 1))

if __name__ == '__main__':

A = [1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0]

k = 2

findLongestSequence(A, k)

Download Run Code

Output:

The longest sequence has length 10 from index 0 to 9

The time complexity of the above solution is O(n) and doesn’t require any extra space, where n is the size of the given sequence.

Exercise: Extend the solution to print the index of all zeros replaced.