Maximum Consecutive Ones
Given a binary array 'ARR' of size 'N', your task is to find the longest sequence of continuous 1’s that can be formed by replacing at-most 'K' zeroes by ones. Return the length of this longest sequence of continuous 1’s.

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow. The first line of each test case or query contains an integer 'N' representing the size of the array (ARR). The second line contains 'N' single space-separated binary values, representing the elements in the array. The third line contains the value of 'K'.

Output format:

For each test case, return the length of the longest subarray whose all elements are 1.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Maximum Consecutive Ones

Given a binary array 'ARR' of size 'N', your task is to find the longest sequence of continuous 1’s that can be formed by replacing at-most 'K' zeroes by ones. Return the length of this longest sequence of continuous 1’s.

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case or query contains an integer 'N' representing the size of the array (ARR).

The second line contains 'N' single space-separated binary values, representing the elements in the array.

The third line contains the value of 'K'.

Output format:

For each test case, return the length of the longest subarray whose all elements are 1.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 5 * 10^4 
0 <= Arr[i] <= 1
0 <= K <= N

Time Limit: 1 sec

Accepted Answer

I solved this question by 2 pointers by taking left and right pointers and moving the right point untill it was possible to switch the zeroes else move the left pointer

Accepted Answer

Brute Force approach

The simplest way to find the required subarray would be to consider all the possible subarrays and compare the length at every point and store the longest length. If at any point, the current element is 0 and the value of ‘K’ is greater than 0, use it to convert the current element to 1. Else if the value of K is 0 , iterate further to find the next possible subarray.

Algorithm :

Loop over the array and if the current element of the array is ‘1’ find the length of the longest subarray starting with the current element.
If the current element is ‘0’ , and the value of ‘K’ is greater than 0 , use it to convert the current element to ‘1’ and continue.
While considering any particular subarray if the value of any element is 0 and the value of K is greater than 0, reduce K by 1 and consider the current element to be 1.
At every step update the length of the longest subarray of 1’s found so far, print this value at the end.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is required.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of elements in the array.

For each element of the array, the whole array is iterated. So, time complexity will be O(N^2).

Java (SE 1.8)

/*

	Time complexity: O(N^2) 

	Space complexity: O(1)

	

	where 'N' is the total number of elements in the array.

*/



import java.util.ArrayList;



public class Solution {

    public static int longestSubSeg(ArrayList arr, int n, int k) {



        int i = 0, j = 0;

        // Stores the length of longest sub segment with all 1.

        int maxLen = 0;



        // i is the starting index of the subarray under consideration.

        for (i = 0; i < n; i++) {

            int kCopy = k;



            // If the value of current element is 0.

            if (arr.get(i) == 0) {



                // Convert it to 1 if possible.

                if (kCopy > 0) {

                    kCopy--;

                }



                // Otherwise the current subarray can't be a candidate for the solution.

                else {

                    continue;

                }



            }



            // Find the longest subarray with i as the starting index.

            for (j = i + 1; j < n; j++) {

                if (arr.get(j) == 0) {

                    if (kCopy > 0) {

                        kCopy--;

                    } else {

                        break;

                    }

                }

            }



            // Update maximum length.

            maxLen = Math.max(maxLen, j - i);

        }



        return maxLen;



    }

}

C++ (g++ 5.4)

/*

	Time complexity: O(N^2) 

	Space complexity: O(1)

	

	where 'N' is the total number of elements in the array.

*/



int longestSubSeg(vector &arr , int n, int k) 

{ 



    // Stores the length of longest sub segment with all 1.

    int maxLen = 0; 

    int i,j;

  

    // i is the starting index of the subarray under consideration.

    for(i = 0; i < n; i++){

    	int kCopy = k;  	

    	// If the value of current element is 0.

    	if(arr[i] == 0){

    		// Convert it to 1 if possible.

    		if(kCopy > 0){

    			kCopy--;

			}

			

			// Otherwise the current subarray can't be a candidate for the solution.

			else{

				continue;

			}

		}



		// Find the longest subarray with i as the starting index.

    	for(j = i+1; j    		if(arr[j] == 0){

	    		if(kCopy > 0){

	    			kCopy--;

				}

				else{

					break;

				}

			}	

		}

		

		// Update maximum length.

		maxLen = max(maxLen , j-i);	

	}

  

    return maxLen; 

}

Python (3.5)

'''

	Time complexity: O(N^2) 

	Space complexity: O(1)

	

	where 'N' is the total number of elements in the array.

'''



def longestSubSeg(arr, n, k):



    # Stores the length of longest sub segment with all 1.

    maxLen = 0

    i, j = 0, 0



    # i is the starting index of the subarray under consideration.

    for i in range(n):

        kCopy = k



        # If the value of current element is 0.

        if(arr[i] == 0):



            # Convert it to 1 if possible.

            if(kCopy > 0):

                kCopy -= 1



            # Otherwise the current subarray can't be a candidate for the solution.

            else:

                continue



        isEnd = True



        # Find the longest subarray with i as the starting index.

        for j in range(i+1, n):

            if(arr[j] == 0):



                if(kCopy > 0):

                    kCopy -= 1



                else:

                    isEnd = False

                    break



            # Update maximum length.

            if(isEnd == False):

                maxLen = max(maxLen, j-i)

            else:

                maxLen = max(maxLen, j-i+1)



    return maxLen

Accepted Answer

Queue based approach

The idea is to iterate the whole array and push the indices having value as zero of the subarray considered in a queue. Keep on iterating the array until the size of the queue is less than ‘K’. When the size of the queue becomes equal to ‘K’, update the starting index of the subarray under consideration and pop an element from the queue and push the value of current index in the queue. Check at every step for maximum size.

Algorithm :

Loop over the array and keep a mark of the starting index of the subarray under consideration and take an empty queue.
If the value at current index of array is 0, check the size of the queue:
a. If the size of the queue is less than ‘K’, push the index.
b. Else update the value of the starting index as the next index present at the front of the queue, pop the front value of the queue and push the current index at the back.
At every step update the length of the longest subarray of 1’s found so far, print this value at the end.

Space Complexity: OtherExplanation:

O(K), where ‘K’ is the maximum number of replacements that can be done.

The maximum size of the queue at any point of time can be ‘K’. Thus, the final space complexity is O(K).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of elements in the array.

The array is iterated once. So, time complexity will be O(N).

Java (SE 1.8)

/*

    Time complexity: O(N) 

	Space complexity: O(K)

	

	where 'N' is the total number of elements in the array and 'K' is the maximum number of replacements allowed from 0 to 1.

*/



import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;



public class Solution {



    public static int longestSubSeg(ArrayList arr, int n, int k) {



        // Starting index of array under consideration.

        int l = 0;

        int max_len = 0;

        Queue q = new LinkedList<>();

        // To store current size of the queue.

        int size = 0;



        // i decides current ending point, i.e. the right pointer.

        for (int r = 0; r < n; r++) {

            if (arr.get(r) == 0) {

                q.add(r);

                size++;

            }



            // Updating queue when its size becomes greater than k.

            if (size > k) {

                // Updating starting index of array under consideration.

                l = q.peek() + 1;

                q.remove();

                size--;

            }



            max_len = Math.max(max_len, r - l + 1);

        }



        return max_len;

    }



}

C++ (g++ 5.4)

/*

	Time complexity: O(N) 

	Space complexity: O(K)

	

	where 'N' is the total number of elements in the array and 'K' is the maximum number of replacements allowed from 0 to 1.

*/



#include



int longestSubSeg(vector &arr , int n, int k) 

{ 



    // Starting index of array under consideration.

    int l = 0;

    int max_len = 0; 

    queueq;

    // To store current size of the queue. 

    int size = 0;

  

    // i decides current ending point, i.e. the right pointer.	

    for (int r = 0; r < n; r++) { 

        if (arr[r] == 0){

            q.push(r);

            size++;

        } 

        

        // Updating queue when its size becomes greater than k.        

        if (size > k) { 

            // Updating starting index of array under consideration.

            l = q.front() + 1;

            q.pop();

            size--;

        } 

  

        max_len = max(max_len, r - l + 1); 

    }



    return max_len; 

}

Python (3.5)

'''

	Time complexity: O(N)

	Space complexity: O(K)



	where 'N' is the total number of elements in the array and 'K' is the maximum number of replacements allowed from 0 to 1.

'''



from collections import deque



def longestSubSeg(arr, n, k):



    # Starting index of array under consideration.

    l = 0

    max_len = 0

    q = deque()

    # To store current size of the queue.

    size = 0



    # i decides current ending point, i.e. the right pointer.

    for r in range(n):

        if (arr[r] == 0):

            q.append(r)

            size += 1



        # Updating queue when its size becomes greater than k.

        if (size > k):

            # Updating starting index of array under consideration.

            l = q.popleft() + 1

            size -= 1



        max_len = max(max_len, r - l + 1)



    return max_len

Accepted Answer

Two - Pointer approach

The idea is to use Two - Pointer approach. Let us take a subarray [l,r] which contains at-most ‘K’ zeroes. Let our left pointer be ‘l’ and right pointer be ‘r’. We always maintain our subsegment [l,r] to contain no more than ‘K’ zeroes by moving the left pointer ‘l’ accordingly. Check at every step for maximum size i.e. ‘r-l+1’.

Algorithm :

Take two pointers ‘l’ and ‘r’ representing left and right pointers respectively. Initialize both the pointers with 0.
Keep on moving the right pointer ‘r’ until the count of 0’s in the subarray represented by [l,r] is less than equal to ‘K’ (maximum replacements possible).
When the count of 0’s becomes more than ‘K’ shorten the subarray by incrementing the left pointer ‘l’ so that the count of 0’s in subarray [l,r] becomes equal to ‘K’.
At every step update the length of the longest subarray found so far, print this value at the end.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is required.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of elements in the array.

There are two pointers traversing the whole array, so in the worst case both the pointer can reach the end of the array thus the time complexity will be O(N+N) = O(2*N) = O(N).

Python (3.5)

'''

	Time complexity: O(N)

	Space complexity: O(K)



	where 'N' is the total number of elements in the array and 'K' is the maximum number of replacements allowed from 0 to 1.

'''



from collections import deque



def longestSubSeg(arr, n, k):



    # Starting index of array under consideration.

    l = 0

    max_len = 0

    q = deque()

    # To store current size of the queue.

    size = 0



    # i decides current ending point, i.e. the right pointer.

    for r in range(n):

        if (arr[r] == 0):

            q.append(r)

            size += 1



        # Updating queue when its size becomes greater than k.

        if (size > k):

            # Updating starting index of array under consideration.

            l = q.popleft() + 1

            size -= 1



        max_len = max(max_len, r - l + 1)



    return max_len

C++ (g++ 5.4)

/*

	Time complexity: O(N) 

	Space complexity: O(1)

	

	where 'N' is the total number of elements in the array.

*/



int longestSubSeg(vector &arr , int n, int k) 

{ 



	// Stores count of zero in the array under consideration.

    int cnt0 = 0;

    int l = 0; 

    int maxLen = 0; 

  

    // r decides current ending point, i.e. the right pointer.

    for (int r = 0; r < n; r++) { 

        if (arr[r] == 0) {

            cnt0++; 

        }

  

        // If there are more 0's move left pointer towards current ending point. 

        while (cnt0 > k) { 

            if (arr[l] == 0) {

                cnt0--; 

            }



            l++; 

        } 

  

        maxLen = max(maxLen, r - l + 1); 

    }

	

    return maxLen; 

}

Java (SE 1.8)

/*

    Time complexity: O(N) 

	Space complexity: O(1)

	

	where 'N' is the total number of elements in the array.

*/



import java.util.ArrayList;



public class Solution {

    public static int longestSubSeg(ArrayList arr, int n, int k) {

        // Stores count of zero in the array under consideration.

        int cnt0 = 0;

        int l = 0;

        int maxLen = 0;



        // r decides current ending point, i.e. the right pointer.

        for (int r = 0; r < n; r++) {

            if (arr.get(r) == 0) {

                cnt0++;

            }



            // If there are more 0's move left pointer towards current ending point.

            while (cnt0 > k) {

                if (arr.get(l) == 0) {

                    cnt0--;

                }



                l++;

            }



            maxLen = Math.max(maxLen, r - l + 1);

        }



        return maxLen;

    }

}

Given a binary array 'ARR' of size 'N', your task is to find the longest sequence of continuous 1’s that can be formed by replacing at-most 'K' zeroes by ones. Return the length of this longest sequence of continuous 1’s.

Input format:

Output format:

Note:

Constraints:

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer