The problem asks to find out the largest subarray of consecutive ones where k zeros can be flipped at most.
This can also be interpreted as finding the largest subarray with at most k zeros.
This can be done with the two-pointer sliding window pattern:
Find the largest subarray/substring with <condition>
Brute force approach:
class Solution {
public int longestOnes(int[] nums, int k) {
//This can be like finding the longest subarray with at most k zeros
//that would mean that we have the longest subarray having only k zeros
//which upon flip to 1 will make/create the longest consecutive ones in the array
//brute force approach:
int n = nums.length;
int maxLen = 0;
for(int i =0;i<n;i++){
int count =0;
for(int j = i;j<n;j++){
if(nums[j]==0){
count++;
if(count>k) break;
}
maxLen = Integer.max(maxLen, j-i+1);
}
}
return maxLen;
}
}
Better approach :
Two-pointer sliding window approach:
pattern: find the largest subarray/substring with
TC: O(n) + O(n) n for a right pointer moving right, and O(n) In the worst case left will move from 0 to n-1 index for the given right pointer index,
note: it will never be O(n^2) because the left is not always moving, it is moving to a certain index in certain conditions only ( count of zero > k)
//O(2N)
class Solution {
public int longestOnes(int[] nums, int k) {
///this can be understood as finding the longest subarray with at most k 0's
//Which is nothing but the two-pointer pattern: find the largest subarray/substring with <condition>
//The standard pattern for solving such a pointer sliding window problem is below:
int left =0,right = 0;
int count = 0;
int n = nums.length;
int len = 0,maxLen = 0;
while(right < n){
if(nums[right] ==0) count++;
while(count>k){
if(nums[left]==0) count--;
left++;
}
if(count<=k)
maxLen= Integer.max(maxLen, right-left+1);
right++;
}
return maxLen;
}
}
Optimal approach:
Instead of using the while loop inside which runs till the count is greater than k ( count of 0)
We can only shift the left pointer once at a time; it doesn’t matter if the count of 0 decreases or not.
this will make sure that the time complexity is O(n) unlike in above case where the time complexity is O(2N)
class Solution {
public int longestOnes(int[] nums, int k) {
///this can be understood as finding the longest subarray with at most k 0's
//Which is nothing but the two-pointer pattern: find the largest subarray/substring with <condition>
//The standard pattern for solving such a pointer sliding window problem is below:
int left =0,right = 0;
int count = 0;
int n = nums.length;
int len = 0,maxLen = 0;
while(right < n){
if(nums[right] ==0) count++;
if(count>k){
if(nums[left]==0) count--;
left++;
}
if(count<=k)
maxLen= Integer.max(maxLen, right-left+1);
right++;
}
return maxLen;
}
}
Top comments (0)