Max consecutive one's III

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>

Problem

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;
    }
}

Blog

Max consecutive one's III

Prashant Mishra

Join Our Newsletter. No Spam, Only the good stuff.

Related