L4. Max Consecutive Ones III | 2 Pointers and Sliding Window Playlist

[ouuualo]

Solved by myself before but can't skip your video. Nice one!

[animexworld]

I may not comment on all your video. But I do watch them till last

[krishnavamsiyerrapatruni]

I've always had a problem with two pointer + sliding window problems. I've solved a few in Leetcode by reading the editorials. I understood them at that point of time but couldn't apply them again in the future as I just couldn't wrap my head around them. But now the intuition kicked in after watching the first few videos of your playlist and I'm able to visualise the algo while solving problems. Thank you so much!!! :)

[studyafa]

3:43 brute
4:45 brute code

7:55 better
13:45 better code
17:00 better T(0)


19:20 best
24:46 - 26:48 best code

[tanujaSangwan]

Unbelievable! I solved it entirely on my own in just 5 minutes using a priority queue. Now, time to watch the video.

[AbhijayaPal-dqzt]

sliding window and two pointer approach best playlist, thank you so much raj (our striver)

[AkshatMehra-lb]

Good video ! Wasn't expecting the last solution, took me some time to think but definitely made my brain work.
The main logic is that once we have found a subarray with 2 zeros of size 5, as discussed in example, and a subarray with 2 zeros of size 6 exists... then once we reach subarray of size 5, we do not shrink our sliding window. And we keep moving it ahead by moving both left and right pointers. Once we reach the subarray of size 6, our sliding window's right pointer is updated while left keeps calm, and sliding window size is updated to 6. I hope it helps.

[shibainu]

OMG i solved it by myself. Idk if it was an easy question but your lectures are super helpful.

[baldevsundarani]

You are the best striver, solving two pointer became very easy after seeing your videos.

[akshatdubey]

I could implement this myself in the first try, thanks for helping me gain confidence raj.

[dhineshkumard]

class Solution {
public int longestOnes(int[] nums, int k) {
int l=0, r=0, max=0, zero=0, n=nums.length;
while(r<n){
if(nums[r]==0) zero++;
if(zero>k){
if(nums[l]==0) zero--;
l++;
}
if(zero<=k){
max=Math.max(max, r-l+1);
}
r++;
}
return max;
}
}

[PrinceKumar-efxf]

00:06 Solving the problem of finding the maximum consecutive ones with at most K zeros.
02:57 Using sliding window to find longest subarray with at most K zeros
07:43 Using sliding window to find maximum consecutive ones with K zeros.
10:13 Using sliding window technique to manage consecutive ones and zeros efficiently
15:10 Use a sliding window technique to handle scenarios with more zeros than K.
17:40 Optimizing Max Consecutive Ones III using sliding window technique
22:01 Illustration of updating max consecutive ones with sliding window approach
24:13 Algorithm to find max consecutive ones after K flips.
28:58 Algorithm works with time complexity of O(n) and space complexity of O(1).

[ShahNawaz-cxpi]

Another Approach:-
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {

int size = nums.size();
int l = 0;
int r = 0;
vector<int>ind;
int i = 0;
int ans = 0;

for(int i = 0;i<size;i++){
if(nums[i]==0)
ind.push_back(i);
}

while(r<size) {
if(nums[r]==0){
if(k==0)
l = ind[i++]+1;
else
k--;
}
ans = max(ans, r-l+1);
r++;
}

return ans;

}
};

[namannema]

these explaining style is good striver please make more videos like that only

[Cool]

Thankyou so much Striver for all you efforts throughout in delivering us so much valuable content. Any student / working professional can now be able to transition their career without paying money for courses.

Would also like your insights on the point :

While preparing for interviews most of the aspirants are going through the videos solely and solving the question after completely watching the video. And also are feeling lazy trying to solve the question on our own. What is the best way to complete any topic without being lazy and how should an aspirant approach any topic/playlist?

[TanmayDwivedi-tulv]

another approach


class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size(); // Get the size of the input vector
int ans = 0; // Variable to store the maximum length of subarray with at most k zeros
int ct = 0; // Variable to count the number of zeros encountered
vector<int> v1; // Vector to store the cumulative count of zeros

// Traverse the input vector to fill the cumulative count of zeros
for (int i = 0; i < n; i++) {
if (nums[i] == 0) {
ct++; // Increment the count if the current element is zero
}
v1.push_back(ct); // Add the cumulative count to the vector
}

int j = 0; // Left pointer of the sliding window
int g = k - 1; // Right pointer of the sliding window
if (k == 0) {
g = 0; // Handle edge case when k is 0
}

// Traverse the input vector using the sliding window approach
while (g < n && g < v1.size()) { // Ensure g does not go out of bounds
// Calculate the number of zeros in the current window
int temp = v1[g] - (j > 0 ? v1[j - 1] : 0);
if (temp <= k) { // Check if the number of zeros is within the allowed limit
ans = max(ans, g - j + 1); // Update the answer if the current window is larger
g++; // Expand the window by moving the right pointer
} else {
j++; // Shrink the window by moving the left pointer
}
}
return ans; // Return the maximum length of subarray with at most k zeros
}
};

[expanse]

another way can be use sum to count no of ones and check if len-sum >k, reduce sum if nums[l]=1, update l and find maxlen

[SahilRaj-ypzu]

we can also use a queue instead of nested loop,
Here the time complexity is O(N), and the space complexity is O(N)
int max =0, l=0, r=0;
Queue<Integer> index =new LinkedList<>();
int zero =0;
while(r<n){
if(arr[r]==0){
index.add(r);
zero++;
if(zero>k){
l=index.poll() +1;
zero--;
}
}

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

} hope you like my solution🙂

[nmwcttu]

class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
// Brute force
int length = 0;
int maxLen = 0;
for(int i=0;i<nums.size();i++){
int zeros = 0;
for(int j=i;j<nums.size();j++){
if(nums[j] == 0) zeros++;
if(zeros<=k){
length = j - i + 1;
maxLen = max(length, maxLen);
}
else break;
}
}
return maxLen;

// Sliding window
int n = nums.size();
int left = 0, right = 0, length = 0, maxLength = 0, zeros = 0;
while(right<n){
if(nums[right] == 0) zeros++;
while(zeros>k){
if(nums[left] == 0) zeros--;
left++;
}
if(zeros<=k){
length = right - left + 1;
maxLength = max(length, maxLength);
}
right++;
}
return maxLength;

// Optimal
int n = nums.size();
int left = 0, right = 0, length = 0, maxLength = 0, zeros = 0;
while(right<n){
if(nums[right] == 0) zeros++;
if(zeros>k){
if(nums[left] == 0) zeros--;
left++;
}
if(zeros<=k){
length = right - left + 1;
maxLength = max(length, maxLength);
}
right++;
}
return maxLength;
}
};

[hashcodez]

"UNDERSTOOD BHAIYA!!"
Mza aagya