Given a binary array a[] or size N and an integer K, the task is to find the longest subarray consisting of only 1s or only 0s when at most K elements can be flipped (i.e change 1 to 0 or 0 to 1).
Examples:
Input: a[] = {1, 0, 0, 1, 1, 0, 1}, K = 1.
Output: 4
Explanation: Flip element of index 0(0-based index) to 0.
Then the maximum subarray with all 0 will be of length 3 [0-2]
Flip index 5 to 1. The maximum subarray with all 1’s will be of length 4 [3-6]
So the maximum of (3, 4) is 4. So the answer is 4 for this test case.Input : a[] = {1, 0, 0, 1, 0, 1, 0, 1, 0, 1}, K = 2.
Output : 6
Explanation: Flip 2-1’s to 0 or 2-0’s to 1.
So after flipping element of index 6 and 8 to 1,
the maxlength of the subarray consisting of only 1’s is 5 [5 to 9].
Flip element of index 3 and 5 to 0 then the maxlength
of the subarray consisting of only 0’s is 6 [1 to 6]
The maximum of both of them is 6. So the answer is 6 for this input.
Approach: This problem can be solved using two pointers approach and sliding window algorithm based on the following idea.
Run for loop two times –
- One loop to maintain subsegment [l, r] to contain not more than K 0s and find maximum length of subarray containing only 1s and
- Second loop to maintain subsegment [l, r] to contain not more than K 1s and find maximum length of subarray containing only 0s.
Then return maximum of the both lengths.
Follow the given steps to solve the problem:
- Finding the longest subarray containing only 1s with at most K -flips:
- Declare variable cnt and an integer pointer left which will point at index 0 in the beginning.
- Now run a loop from 0 to N and at any position:
- If arr[i] equals 0, then increase the cnt variable.
- At any position, if the cnt is greater than K, move the left pointer to the right side and again check if arr[left] equals 0,
- Then decrease the cnt variable and run this loop until cnt is greater than K.
- Store the maximum length of subarray containing only 1’s and calculate this length as (current index – left pointer + 1).
- Find the longest subarray containing only 0s with at most K-flips and store its length in the similar way.
- Return the maximum among both of the maximum lengths.
Below is the implementation for the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the longest subarray// following the given conditionsint longestSubSeg(int arr[], int N, int K){ int cnt = 0; int left = 0; int maximum_len1 = 0; int maximum_len0 = 0; // Finding length of maximum subarray // containing 1's only with atmost k flips for (int i = 0; i < N; i++) { if (arr[i] == 0) cnt++; while (cnt > K) { if (arr[left] == 0) cnt--; left++; } maximum_len1 = max(maximum_len1, i - left + 1); } // Set these variables to 0 for further use cnt = 0; left = 0; // Finding length of maximum subarray // containing 0's only with atmost k flips for (int i = 0; i < N; i++) { if (arr[i] == 1) cnt++; while (cnt > K) { if (arr[left] == 1) cnt--; left++; } maximum_len0 = max(maximum_len0, i - left + 1); } return max(maximum_len1, maximum_len0);}// Driver codeint main(){ int arr[] = { 1, 0, 0, 1, 0, 1, 0, 1 }; int K = 2; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << longestSubSeg(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the longest subarray // following the given conditions static int longestSubSeg(int arr[], int N, int K) { int cnt = 0; int left = 0; int max_len1 = 0; int max_len0 = 0; // Finding length of maximum subarray // containing 1's only with atmost k flips for (int i = 0; i < N; i++) { if (arr[i] == 0) cnt++; while (cnt > K) { if (arr[left] == 0) cnt--; left++; } max_len1 = Math.max(max_len1, i - left + 1); } // Initialize with again 0 for further use left = 0; cnt = 0; // Finding length of maximum subarray // containing only 0's with atmost k flips for (int i = 0; i < N; i++) { if (arr[i] == 1) cnt++; while (cnt > K) { if (arr[left] == 1) cnt--; left++; } max_len0 = Math.max(max_len0, i - left + 1); } return Math.max(max_len1, max_len0); } // Driver code public static void main(String[] args) { int a[] = { 1, 0, 0, 1, 0, 1, 0, 1 }; int K = 2; int N = a.length; // Function call System.out.println(longestSubSeg(a, N, K)); }} |
Python3
# Python program for the above approach# Function to find the longest subarray# following the given conditionsdef longestSubSeg(arr, N, K): cnt = 0 left = 0 maximum_len1 = 0 maximum_len0 = 0 # Finding length of maximum subarray # containing 1's only with atmost k flips for i in range(0, N): if (arr[i] == 0): cnt = cnt+1 while (cnt > K): if (arr[left] == 0): cnt = cnt-1 left = left+1 maximum_len1 = max(maximum_len1, i - left + 1) # Set these variables to 0 for further use cnt = 0 left = 0 # Finding length of maximum subarray # containing 0's only with atmost k flips for i in range(0, N): if (arr[i] == 1): cnt = cnt+1 while (cnt > K): if (arr[left] == 1): cnt = cnt-1 left = left+1 maximum_len0 = max(maximum_len0, i - left + 1) return max(maximum_len1, maximum_len0)# Driver codearr = [1, 0, 0, 1, 0, 1, 0, 1]K = 2N = len(arr)# Function callprint(longestSubSeg(arr, N, K))# This code is contributed by Taranpreet |
C#
// C# program for the above approachusing System;public class GFG { // Function to find the longest subarray following the // given conditions static int longestSubSeg(int[] arr, int N, int K) { int cnt = 0; int left = 0; int max_len1 = 0; int max_len0 = 0; // Finding length of maximum subarray containing 1's // only with atmost k flips for (int i = 0; i < N; i++) { if (arr[i] == 0) cnt++; while (cnt > K) { if (arr[left] == 0) cnt--; left++; } max_len1 = Math.Max(max_len1, i - left + 1); } // Initialize with again 0 for further use left = 0; cnt = 0; // Finding length of maximum subarray containing // only 0's with atmost k flips for (int i = 0; i < N; i++) { if (arr[i] == 1) cnt++; while (cnt > K) { if (arr[left] == 1) cnt--; left++; } max_len0 = Math.Max(max_len0, i - left + 1); } return Math.Max(max_len1, max_len0); } static public void Main() { // Code int[] a = { 1, 0, 0, 1, 0, 1, 0, 1 }; int K = 2; int N = a.Length; // Function call Console.WriteLine(longestSubSeg(a, N, K)); }}// This code is contributed by lokesh (lokeshmvs21). |
Javascript
<script> // JavaScript program for the above approach // Function to find the longest subarray // following the given conditions const longestSubSeg = (arr, N, K) => { let cnt = 0; let left = 0; let maximum_len1 = 0; let maximum_len0 = 0; // Finding length of maximum subarray // containing 1's only with atmost k flips for (let i = 0; i < N; i++) { if (arr[i] == 0) cnt++; while (cnt > K) { if (arr[left] == 0) cnt--; left++; } maximum_len1 = Math.max(maximum_len1, i - left + 1); } // Set these variables to 0 for further use cnt = 0; left = 0; // Finding length of maximum subarray // containing 0's only with atmost k flips for (let i = 0; i < N; i++) { if (arr[i] == 1) cnt++; while (cnt > K) { if (arr[left] == 1) cnt--; left++; } maximum_len0 = Math.max(maximum_len0, i - left + 1); } return Math.max(maximum_len1, maximum_len0); } // Driver code let arr = [1, 0, 0, 1, 0, 1, 0, 1]; let K = 2; let N = arr.length; // Function call document.write(longestSubSeg(arr, N, K)); // This code is contributed by rakeshsahni</script> |
Output
6
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
