LeetCode Max Consecutive Ones III Solution Explained

LeetCode Max Consecutive Ones III Solution Explained - Java

Рет қаралды 34,879

4 жыл бұрын

The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow Me on X/Twitter - x.com/nickwhitereal
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering

Пікірлер: 44

@artur4427 6 ай бұрын

what helped me understand this is the realization that i and j are not the actual edges of the longest consecutive segment. the window never shrinks, so the max length is kept track of implicitly by the window's size.

@danielpark4204 3 жыл бұрын

took a while but i get it now, however I think its more intuitive to just cache the maxLen in a variable and shrink until K is positive again rather than caching the width throughout.

@aj9706 2 жыл бұрын

Yes absolutely

@tapanbasak1453 3 жыл бұрын

Can anyone please explain why i-j always gives the correct result without keeping track of the max subarray at all times.

@HoangLe-qr9si 3 жыл бұрын

i think that was handled by if k is positive then j will not increase

@user-le6ts6ci7h 2 жыл бұрын

It is because , as long as you are able to get contiguous 1 , with maximum k flips of zero, the i value goes on increasing and j remains at the position so far. And once the k becomes negative( that is, k+1 zeros are flipped) then both j and i are incremented , meaning that j-i is still fixed in length and equal to the size of contiguous 1 found so far . So actually this maximum fixed size windows is moving throughout the array which is always expanding rather than contracting

@luz8011 2 жыл бұрын

@@user-le6ts6ci7h thank u for explaining it :)

@amansaxena4446 Жыл бұрын

not making sense at all

@subhamshaw1726 3 жыл бұрын

that was really simple, great explanation

@MrThepratik 4 жыл бұрын

Getting my head around it

@gitanjalikumari9262 3 жыл бұрын

So nice solution 👍😊

@vijayakumareyunni6010 7 ай бұрын

Key thing to be explained is how the pointers are to be updated which was not explained clearly. He also got confused when coding and somehow it worked.

@SnehaBharathiReddy 3 ай бұрын

Straight forward Explanation. Thanks Nick

@ayusheeagarwal955 Ай бұрын

Can someone explain why are we returning i - j instead i - j + 1.

@mehdihassan93 Күн бұрын

for people who are looking for python3 solution: l = 0 for r in range(len(nums)): if nums[r] == 0: k -= 1 if k < 0: if nums[l] == 0 : k += 1 l += 1 r += 1 return r - l

@miaohong601 4 жыл бұрын

This is much easier to understand than the most upvoted in discussion, Thanks Nick!!

@rajatsrivastava555 2 жыл бұрын

clean and not fancy!!

@aayush5474 3 жыл бұрын

whats the timecompleity?

@mikea3264 3 жыл бұрын

O(n) because there is just one loop going through the whole array.

@akshittyagi1784 2 жыл бұрын

2 mins and 30 seconds into the video, and Nick's like enough talk, let's just get straight to business😂😂 respect man👍

@emerylin6793 2 жыл бұрын

while the code is simple, you dont get the longest number of ones, which is not the right answer.

@mohammedghabyen721 2 жыл бұрын

public class Solution { public int LongestOnes(int[] nums, int k) { int left=0; int right=0; int ck = k; int maxNu = 0; while(right0) { ck--; right++; }else{ if(nums[left]==0) { ck++; left++; }else left++; } } maxNu = Math.Max(maxNu,right-left); } return maxNu; } }

@kakwancheng9493 Жыл бұрын

This logic is really clear, thanks a lot!!!

@edwardnewgate2198 4 жыл бұрын

What about the test case "0011111000"- and with K as 2? In that case- j wouldn't be able to reach a 0. How would we get the answer in that case??

@chaoschao9432 4 жыл бұрын

j will reach 0, you may run the test case step by step.

@MrSaiyah007 4 жыл бұрын

@@chaoschao9432 it will not

@ArtInMotion6912 4 жыл бұрын

Yup but the size is same both j and i increments so no effect on it

@ashutoshchauhan4928 3 жыл бұрын

I had the same doubt, thanks for giviing the rationale behind it @brock lesner

@sarscov9854 3 жыл бұрын

it works. I put it in the compiler, gave me 7.

@comedycentral4333 2 жыл бұрын

What would be this test case "1110" if k = 1 the output will be 3 right, but the above code returning 4, can anyone please suggest me?

@user-le6ts6ci7h 2 жыл бұрын

No , the answer would be 4. At the end of the loop i will be having a value 4, the reason of which it exits the loop. And j will be at 0 .So returns 4-0

@deepakbisht7764 2 жыл бұрын

4 is correct as k =1 so we can flip single 0 so if you flip last 0 the longest continuation will be 1111 so result should be 4 not 3...

@tejapvs 10 ай бұрын

@@user-le6ts6ci7h Got It, Thinking for a whie how he got 4, didnt observe he was increaing i

@ronaldabellano5643 4 жыл бұрын

The solution seems easy.

@sujayshanbhag2055 10 ай бұрын

What happens if i reaches end before k becomes positive?

@sujayshanbhag2055 10 ай бұрын

I think this is more Intuitive : - int longestOnes(vector& nums, int k) { int last=0; int first=0; int n=nums.size(); int maxLen=0; while(last< n) { if(nums[last]==0) k--; while(k

@sujayshanbhag2055 10 ай бұрын

Intuition behind the code in the video: This is notes I made for me, but if it helps you, great!. Above code: Whenever the number of zeros taken exceeds k, move the starting point of window until we recover the 0. In video code: We don't run a loop to recover the 0. Whenever we take in a bad zero, we increment the start. By doing this whenever, we increment last, first gets incremented and we maintain the length. [We do not keep track of the actual sub array]. If we recover the 0 in process, only last will start to increment, increasing the length of the subarray.