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)