Patching Array | Thought Process | Dry Runs | GOOGLE | Leetcode 330 | codestorywithMIK
Вставка
- Опубліковано 14 чер 2024
- Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 35th Video of our Playlist "Greedy Technique : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good greedy Problem : Patching Array | Thought Process | Dry Runs | GOOGLE | Leetcode 330 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Patching Array | Thought Process | Dry Runs | GOOGLE | Leetcode 330 | codestorywithMIK
Company Tags : GOOGLE
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/patchin...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Key Concepts:
Maximum Reach (maxReach):
maxReach represents the largest sum that can be formed using the current set of numbers from nums and any patches added so far.
Iterating Through nums:
We iterate through the nums array to incrementally build up the range of sums that can be formed. If the current number nums[i] is within the next achievable range (less than equal to maxReach + 1), we add it to maxReach and move to the next number.
Adding Patches:
Whenever a gap is detected (i.e., nums[i] is greater than maxReach + 1), we add a patch. The most efficient patch is maxReach + 1, which extends the achievable range maximally.
Loop Until maxReach Covers n:
The loop continues until maxReach reaches or exceeds n.
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024
00:02 Leetcode 330: Patching Array - Solve without fancy data structures
02:29 Explaining the concept of patching an array by adding elements to form a sequence from 1 to n
06:38 Patch Missing Array Numbers with 2 or 3
08:39 Importance of taking smaller numbers for patching arrays
12:34 Incrementing the maximum reachable number by adding a patch
14:45 Explanation of Patching Array and Maximum Reachable
18:23 Understanding maximum reach force in array patching
20:27 Calculating reach of array elements through Dry Runs
24:07 Patching strategy based on max reach and current number comparison
26:18 Explanation of the patching process and reaching the target number.
30:32 Algorithm for finding max reach and steps in array problem
Crafted by Merlin AI.
bhaiya, pls start giving the contests solution as well🙏
++
yes ++
Yes please
Also teach segment tree. Qn-4 is based on it
Yea
++
This feels like a Math problem. A tough intuition to come up with.
Segment tree padha do bhaiya pls ajj bhi 4th wala Q's Nehi hua 😢pls padha do segment tree
Yes please
Yess
Aap k video ka he wait kar raha tha kyu ki subha se sub videos dekh liya koi itne ache se nahi samjhaya tha ... you're the best !!!! ❤
Same bro
Bhai same code maina likha mera saara testcase pass nhi hua?
Anyone who is thinking how to proove this greedy
let me give you a proof(or another approach)
what we will be doing is
at some index we will be deficit by some number now there may be case we can fulfil by adding number less than required number
but we may think of adding largest number as possible such that it may help to form more sum as possible ( this may be more greedy approch easy to think)
for eg
in 1 2
we require 4 we can fuillfill by adding 1 only but if we add max number as possible here 4 it may form more sum and my reach our answer as fast as possible
this can be another approach but code will be same ( sort of proof it is)
Very good explanation. Thank you for uploading this
Thank you for making yet another hard to easy.
Also please teach segment tree. I like your teaching
Nice explanation sir ji 🔥🚒
One of the best channel for dsa
nice intuation to thought about question
woow what a explanation just brilliant
Superb explanation!
bhai ur way is the best among all others!
Solved this problem with slightly diff approach but same observation. Thanks for your solution. WE can easily check from below case time complexity : max( O(len), O(logN))
class Solution {
public int minPatches(int[] nums, int n) {
int idx = 0;
long lookingFor = 1;
int count = 0;
while (idx < nums.length && lookingFor lookingFor) {
count++;
lookingFor = 2 * lookingFor;
} else if (nums[idx] < lookingFor) {
lookingFor = lookingFor + nums[idx];
idx++;
} else {
lookingFor = 2 * lookingFor;
idx++;
}
}
while (lookingFor
Best explanation for the question!!!
really like the way you elobrate..
one of the best ques and best explanation
log(n) here seems to be the best case time complexity when the elements in the array tend to be 0 (they cannot be just tend to 0). Then the loop will always go to else condition.
However, for worst case time complexity, lets consider nums[i] = {1,1,1,1,1,1} and n=6. Here maxReach will grow linearly with the size of nums array. And hence the worst case time complexity should be O(n).
thanks for the video really helpful with great concept 🥰
Great Explanation bhaiya as always:) Thanks a lot for this video
awesome explanation thanks!!
Thanks a lot bhaiya ❤❤
Hats off 🙌
very good Q and Soln
Thanks a lot.
wow bhaiya 🤩, what an explaination from hard to easy. really loved that!!!!❤❤
Thank you❤
LeetCode: another hard question, will it break your streak today?
Me : back to back Hard ques might cause me little trouble.
LeetCode: But would you lose?
NAH I'D WIN
DOMAIN EXPANSION🤞 : CodestorywithMIK's explanation!
thank you ❤❤❤❤❤❤
thnx 😄
soon to reach 52k subs
Good morning bhaiya
contest solution please
you made it look so simple , but I messed it before
Thanks a kot
Bhaiya please create a complete playlist for learning dsa along with the videos you already have and add a few more videos teaching concepts which you have not yet covered till now. I would have been 10x better in solving problems had I been able to learn complete dsa from you.
Plz give the explaination video for problem 3 of today's contest
please also make video for leetcode contest 3rd and 4th questions
🤩
legend
Bhaiya please, segment tree lectures in Cpp and Java.
pleasee make a video on segment tree or Finwik tree🙏
Bro can you also explain leetcode contest questions?
Please provide contest solution
Beautifully explained the concept but this code didn't passed all the testcases. You have to make little changes in it
Bhaiya please Solve & explain LC 174. Dungeon Game.
It is quite tricky 🫡🫡
plz make video on third question leetcode contest 402
sir how to develop such intuition ?
this ques is same as 2952. Minimum Number of Coins to be Added.
inc ur ques count.
where do you work MIK??can we connect on LinkedIN?
Bhaiya please make a vid on last contest q3 spell wala wo samaj nahi aarha kahi se bhi recursive way nahi karaya kisi ne uska
man this qs me i got 0 intuition literally... itne qs kr liya lekin kuch intuition nhi aya qs padke... 🙂 kaise hoga accha company crack
sir plz provide contest solution
we all need them
guys plz like this if u want contest solution
segment tree Fenwick tree sikha do boss last 5 6 contests me 4th qs inpe aa rhe hai😢
Bhaiya please *longest valid parantheses* question bataiye
yes
I was searching for some math here....
I completely misinterpreted this question. I thought that patching means replacijg the element rather than inserting at that position
Please make shorter explanations under 15 minutes
Hello i dont understand if condition maxReach+=nums[i];
when you include an element nums[i],
now you can get the sum till maxReach + nums[i] which he showed here from this timestamp - 18:57 se dekho
contest solutions please 2 and 3rd
/* Solution for ques 2 ---- Contest 403 */
class Solution {
public long countCompleteDayPairs(int[] a) {
int n = a.length;
long cnt = 0;
HashMap map = new HashMap();
for(int i = 0; i < n; i++){
int r1 = a[i] % 24;
int r2 = 24 - r1;
if(r1 == 0){
cnt += map.getOrDefault(0, 0);
}
else if(map.containsKey(r2)){
cnt += map.get(r2);
}
if(map.containsKey(r1)){
map.put(r1, map.get(r1) + 1);
}else{
map.put(r1, 1);
}
}
return cnt;
}
}
Thought process ----> If (a + b) is divisible by k, then (a % k) + (b % k) is also divisible by k. (31 + 41) % 8 then (7 + 1) % 8. let r1 = (a % k) and r2 = (b % k) then 0
I wasn't able to solve it on my own .I was like using dp recursion bla bla .. please help will I ever do DSA efficiently on my own.? Sir can you tell us what made you think like this approach 😢😢
same for me, i tried using recursion, solved it but got TLE
@@jewelchakraborty9717 obviously, as constraints not allow us to use recursion. we need to see for another approach.
@@upcoming_Engineer_ But how do guys come up with such an efficient solution? I was not able to think even a bit about this optimal solution on my own. Does this come up with practice and experience?
Its not intuitive 😢
No voice ?
refresh the page
Just refresh the UA-cam page
Thanks
First comment ❤❤🎉, mike bhaiyaa make a whatsapp group for subscribers pls ❤❤❤
description me jo whatsapp link hai uske alawa bhi koi group h kya ?
@@gui-codes wo whatsapp channel he but me aisa bol rah hu ki aaur ek WhatsApp group chahiye jaha sab log apne idea approch share kar paye questions
Great 🔥
Can you please upload today contest q3 🥹