L4. Max Consecutive Ones III | 2 Pointers and Sliding Window Playlist
Vložit
- čas přidán 25. 03. 2024
- Notes/Codes/Problem links under step 10 of A2Z DSA Course: takeuforward.org/strivers-a2z...
Entire playlist: • Two Pointer and Slidin...
Follow us on our other social media handles: linktr.ee/takeuforward
I may not comment on all your video. But I do watch them till last
sliding window and two pointer approach best playlist, thank you so much raj (our striver)
Solved by myself before but can't skip your video. Nice one!
Lol... Me also😅
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!!! :)
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
Aala11
Another Approach:-
class Solution {
public:
int longestOnes(vector& nums, int k) {
int size = nums.size();
int l = 0;
int r = 0;
vectorind;
int i = 0;
int ans = 0;
for(int i = 0;i
class Solution {
public int longestOnes(int[] nums, int k) {
int l=0,r=0,max=0,zero=0,n=nums.length;
while(rk){
if(nums[l]==0) zero--;
l++;
}
if(zero
Quality teaching brother... love you
these explaining style is good striver please make more videos like that only
I could implement this myself in the first try, thanks for helping me gain confidence raj.
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.
OMG i solved it by myself. Idk if it was an easy question but your lectures are super helpful.
Thank you!
in worst case lets assume all array elements are zero and k=0 it takes still 0(2n) the most optimal one
AWOSOME LECTURE. I SOLVED THIS QUESTION BY MYSELF !!!!
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 index =new LinkedList();
int zero =0;
while(rk){
l=index.poll() +1;
zero--;
}
}
max =Math.max(max, (r-l+1));
r++;
} hope you like my solution🙂
very thankful to you
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?
another approach
class Solution {
public:
int longestOnes(vector& 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 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
Thanks Brother💌
dhanyawad guru ji🙏
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).
Thankyou bhai very Good explanation
Solved it on my own after seeing the brute force. Buit I used a deque making it more simple
class Solution {
public:
int longestOnes(vector& nums, int k) {
int i = 0, j = 0, zeroes = 0;
int ans = INT_MIN, len = 0;
int n = nums.size();
deque q;
while(j < n){
if(nums[j] == 0){
zeroes++;
q.push_back(j);
}
if(zeroes > k){
zeroes--;
int x = q.front();
i = ++x;
q.pop_front();
}
len = j - i + 1;
ans = max(ans, len);
j++;
}
return ans;
}
};
Understood. thanks
Great 🔥😃
class Solution {
public:
int longestOnes(vector& nums, int k) {
// Brute force
int length = 0;
int maxLen = 0;
for(int i=0;i
Thanks
Thanks❤
Great job... putting out this playlist. And, I don't see notes out there in TuF website?? for 2P and Sliding Windw problems
C++ CODE BASED ON THIS LOGIC.
class Solution {
public:
int longestOnes(vector& nums, int k)
{
int n = nums.size();
int left = 0, right = 0, maxlen = 0, count0 = 0;
for(right = 0; right < n; right++)
{
if(nums[right] == 0)
{
count0++;
}
while(count0 > k)
{
if(nums[left] == 0)
{
count0--;
}
left++;
maxlen = max(maxlen, right - left + 1);
}
return maxlen;
}
};
You are amazing....wowwwwwwwwwwwwwwwwwwwwwwwwwwwww
int longestOnes(vector& nums, int k) {
int i = 0, j = 0;
int n = nums.size();
int zero = 0;
int maxi = 0;
while (j < n) {
if (nums[j] == 0) {
zero++;
}
while (zero > k) {
if (nums[i] == 0) {
zero--;
}
i++;
}
maxi = max(maxi, j - i + 1);
j++;
}
return maxi;
}
16:21 if condition is not required while is doing the same thing
understood
change while to if and we trim TC from O(2n) to O(n) . VOILA 👍👍
SOLVED BY MYSELF BUT SKIPPING VIDEO MAY COST ME LOSE OF MOST OPTIMAL SOLUTION ❤🔥❤🔥
Do your previous website also exist? I have notes for questions attached there, I am not able to find it
Understood
int main() {
int size_arr , flips ;
cin >> size_arr >> flips ;
vector arr(size_arr,0) ;
vector arr0(size_arr + 2 ,0);
int count = 0 ;
arr0[count] = -1 ;
for(int i = 0 ; i < size_arr ; i++){
cin >> arr[i] ;
if(arr[i] == 0){count++;
arr0[count] = i ;
}
}
count++;
arr0[count] = size_arr ;
int l = 0 ;
int r = l + flips + 1 ;
int max_len = arr0[r] - arr0[l] - 1 ;
while(r < count + 1){
r++ ; l++ ;
max_len= max(max_len,arr0[r]-arr0[l] - 1) ;
}
cout
i didn't understand one thing
in most optimum sol by the time "R" reaches end "L' has traversed N-k (k is some constant)
so shouldn't time complexity be O(N+N-k) which is same as O(2N)🤔🤔
In GFG the most optimized approach is giving out TLE with some 50 Testcases left out of 500, and the better one which uses two while loops is passing out all the test cases without TLE! WHY IS THAT SO?
🙌🏻
sir I can't understand how to take length like j-i+1 and some times other length
can you give me any idea
TC - O(N)
class Solution {
public int longestOnes(int[] arr, int k) {
int r=0;
int l=0;
int maxlen=0;
int zeroes=0;
while(rk){
if(arr[l]==0){
zeroes--;
}
l++;
}
if(zeroes
Hey, I have 1 question .
What if number of 0's are less than K so we have to flip all zeros and then k-no. of zeros times we have to flip 1 as well, right? How will we able to solve that question?
code have not been updated in striver link
My solution with same logic
class Sliding_window {
public static void main(String[] args) {
int[] arr = {1,1,0,1,1,1,0,1,0,1,1,1,0,1};
int k =2;
int l=0,r=0,zeros =0,max=0;
while(r< arr.length){
if(arr[r] == 0){
zeros++;
}
if(zeros>k){
if(arr[l]==0){
zeros--;
}
l++;
}
if(zerosmax){
max = r-l+1;
}
r++;
}
System.out.println(max);
}
}
god
19:20
18:50 There is a while loop inside another while loop. Then how come Time complexity in worst case is O(n)+O(n) and not O(n^2)?
Because for every element it is not running for n times. Even in worst case , it runs for n times for last element only.
@@RK-Sonide4vr gotcha
@@RK-Sonide4vr still it runs N time inside a N time running while loop so why not n^2?
How is the optimal code running on an example like:
arr = [1,0,1,0,1,0,1,0], k=1.
Isn't the left pointer traversing near about n times as well?
You are asking
If we access value 3 times in one loop it will be 3n
I hope you got why it would be n
How about this solution
public int longestOnes(int[] nums, int k) {
int i=0;
int l=0;
for(i=0;i
public int longestOnes(int[]nums,int k){
int l=0,r;
for(r=0;r
us
I don't know why but whenever i am watching these problem statements of two pointer, the first idea striking on my mind is a dp state🥲...then soon understanding dp is having at least 2 states so gotta optimise it
understood
understood
understood