Sum of Subarray Minimums - Leetcode 907 - Python

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

NeetCodeIO

NeetCodeIO

Күн бұрын

Пікірлер: 83
@ayushman_sr
@ayushman_sr 7 ай бұрын
Raise hand if you still didn't understood it by now 🤚
@theruler1096
@theruler1096 9 ай бұрын
If you face interview question like this, you're not unlucky. You're just dead.
@tryundel
@tryundel 9 ай бұрын
Sorry a noob here... how bad is it to solve it with O(n^2) on an interview?
@anti-tankartur677
@anti-tankartur677 9 ай бұрын
​@@tryundel you're basically showing that you have a grasp on the basics but you're not good enough to optimize solutions. For prestigious companies, I think it's generally perceived as red flag.
@ducthinh2412
@ducthinh2412 9 ай бұрын
@@tryundel The obvious brute force approach is n^2 so you will need to come up with a O(n) solution. The interview is at least 45 mins and if it's just 1 question, after you provide the brute foce, you will be expected to come up with the optimal solution
@haoyu1247
@haoyu1247 9 ай бұрын
you will not be moving forward to next step, even it is an internship position (my experience with one of the FAANG)@@tryundel
@chisomedoka401
@chisomedoka401 9 ай бұрын
what we call "your village people" over here
@davi_singh
@davi_singh 9 ай бұрын
Everytime I think I have a handle on leetcode, I get a question like this one and I wonder why the heck am I so dump. Thanks @NeetCodeIO you have the best explanations
@abrahamlincoln5724
@abrahamlincoln5724 9 ай бұрын
Same reason why I hesitate to apply to jobs in big tech where LC questions are common. How do you solve a question if you never encountered similar question(or pattern) before?
@davi_singh
@davi_singh 9 ай бұрын
@@abrahamlincoln5724 same boat brother, I am shit scared cause of the same thing. Have been grinding LC for 3 months gone through 4 study plans but don't feel ready at all
@soumyajitganguly2593
@soumyajitganguly2593 5 ай бұрын
@@abrahamlincoln5724 you practice enough problems so that its unlikely to be a new pattern
@reckyru
@reckyru 9 ай бұрын
Disgustingly hard problem IMO
@shreehari2589
@shreehari2589 9 ай бұрын
Exactly
@elyababakova2125
@elyababakova2125 9 ай бұрын
crazy question
@hengyulee4319
@hengyulee4319 9 ай бұрын
For the modified code, because when calculating left and right we are computing the distance of two elements and appending/prepending does not affect the distance. Two -inf solve some edge cases and empty the stack (except for the first -inf) in the last iteration of the for loop. Correct me if I am wrong.
@m.varunreddy7365
@m.varunreddy7365 9 ай бұрын
couldnt understand, this q is definitely not medium
@iliadmitriev01
@iliadmitriev01 9 ай бұрын
you could also add -inf only to the back off the arr, this absolute minimum will purge the stack without involving extra code at the end of the algorithm
@coolgamertm4411
@coolgamertm4411 9 ай бұрын
Secret POV : Leetcode daily hard problem help this channel grow more
@codingoak4701
@codingoak4701 9 ай бұрын
The reason that optimization works is, for all the small values that dont get removed from the stack, the result will be dynamically updated for the distance to the ends of the array.
@chiragsrivastava4217
@chiragsrivastava4217 9 ай бұрын
class Solution: def sumSubarrayMins(self, arr: List[int]) -> int: MOD=10**9+7 stack=[-1] res=0 arr.append(0) for i,val in enumerate(arr): while stack and val
@alxolr
@alxolr 9 ай бұрын
Gosh if you get one of this during an interview you are done.
@arunrajput1007
@arunrajput1007 9 ай бұрын
hey @NeetcodeIO i am not sure for any new medium level problem i would be able to come up with a solution in 25 mins and this includes explanation + logic + coding + edgecases + dry run. This is not possible if one has already solved this question before. Just need your thoughts whether this is possible for everyone.
@sankalppatil2994
@sankalppatil2994 9 ай бұрын
Rip I still dont get it
@sproutboot
@sproutboot 9 ай бұрын
Same
@quirkyquester
@quirkyquester 19 күн бұрын
great one! Thank you!!
@jianhuahe4066
@jianhuahe4066 9 ай бұрын
I am wondering for n elements the total combination would be n square. Should it be multiple 2 n times and minus 1? Taking an example: n = 2, there are 3 combo, n =3: there are 7.
@kimmyliu5509
@kimmyliu5509 6 ай бұрын
for the second for loop, when you iterate over a stack. are you iterating it like an array? it seems that you assume you can iterate from the earliest added element all the way to the last added element, which is a queue not a stack. in stack you can only iterate over it via the last added element no?
@sk_4142
@sk_4142 9 ай бұрын
A humbling problem indeed
@coffeebytes3257
@coffeebytes3257 9 ай бұрын
💀 why cant my brain figure this stuff out without help 😭
@lingyundai964
@lingyundai964 9 ай бұрын
more practice more practice we got this
@shawncodinghouse
@shawncodinghouse 7 ай бұрын
It's too complexity for me, though I have solved 243 questions.
@MohammadSohail-j6x
@MohammadSohail-j6x 2 ай бұрын
real
@rohitudamale4091
@rohitudamale4091 2 ай бұрын
Good Explanation!!
@KhyatiSatija
@KhyatiSatija 9 ай бұрын
Hello i have been following you since really long , I usually understand what you teach, but this video was a bit complex for me. But I have done this question. Here's my Python code. Its the same approach as yours, just more simple and brute forced. class Solution: def sumSubarrayMins(self, arr: List[int]) -> int: arr = [float('-inf')] + arr + [float('-inf')] previousSmaller = {} preStack = [] nextStack = [] nextSmaller = {} #hashmap result = 0 MOD = 10 ** 9 + 7 for i in range(len(arr) - 1, -1, -1): while preStack and preStack[-1][1] > arr[i]: j, m = preStack.pop() previousSmaller[j] = i #prev smaller element preStack.append((i, arr[i])) for i in range(len(arr)): while nextStack and nextStack[-1][1] >= arr[i]: j, m = nextStack.pop() nextSmaller[j] = i nextStack.append((i, arr[i])) for i in range(1,len(arr) - 1): minTimes = (i - previousSmaller[i]) * (nextSmaller[i] - i) #number of subarrays for which the element at index i is the minimum result += arr[i] * minTimes result = result % MOD return result # arr - 0 3 4 5 6 1 4 6 7 0 # index - 0 1 2 3 4 5 6 7 8 9 #for handling duplicates,we do >= while calculating for nextSmaller and > in prevSmaller #vice versa will also work
@36saurabh
@36saurabh 2 ай бұрын
Around 14:13, if I understand it correctly, does left always evaluate to 1 on line 10? Correct me if I'm wrong. Since all the elements in the stack before the popped element m at index j will be less than m, hence number of subarrays with m as the smallest element on the left of m will always be 1? Is this correct?
@vaishnavejp9247
@vaishnavejp9247 2 ай бұрын
i had the understanding that monotonic stacks come in handy for problems like NGE because we dont just want to keep track of minimum element youve seen, but how close it is to the current element. that is, the closeness matters as well. but for problems like this, i dont understand why a monotonic stack is even needed? cant i just keep track of the minimum most element seen so far? this and trapping rainwater problem as well. someone pls explain why a stack is needed instead of just using mini pointer
@SickleM
@SickleM 9 ай бұрын
Can't believe I did this in first try!
@upendrakumar-bw1jd
@upendrakumar-bw1jd 6 ай бұрын
Actually i am big fan of neetcode because he is the only one who gives better intitution but this time really want to say this time neetcode fail to explains this problem
@chien-yuyeh9386
@chien-yuyeh9386 9 ай бұрын
Thanks for the amazing video
@dingus2332
@dingus2332 9 ай бұрын
Could this be solved with Segment Tree ?
@sbera87
@sbera87 9 ай бұрын
Stack grows upward, but I get the point
@HeroHunter07
@HeroHunter07 9 ай бұрын
Hard one
@XEQUTE
@XEQUTE 9 ай бұрын
wohoo , you did it!! ( hello from yesterday)
@soumithjavvaji3310
@soumithjavvaji3310 4 ай бұрын
Either getting rejected or giving a O(n^2) solution is predefined , if the interviewer asks this!
@rajchinagundi7498
@rajchinagundi7498 9 ай бұрын
class Solution: def sumSubarrayMins(self, arr: List[int]) -> int: mod=10**9+7 n=len(arr) @lru_cache(maxsize=None) def solve(i, n, mn): if i == n: return 0 curr = arr[i] if curr < mn: mn = curr return (mn + solve(i + 1, n, mn)) % mod sumTotal = 0 for i in range(len(arr)): sumTotal = (sumTotal + solve(i, len(arr), inf)) % mod return sumTotal. Hi Neetcode I wrote this recursive approach and it passes 82/87 test cases, and then fails with memory limit exceeded error, I was wondering it this question is only possible via iterative approach?
@CrabGuyy
@CrabGuyy 9 ай бұрын
every iterative code can be done recursively, i would suggest trying to implement tail recursion because python optimizes it for memory
@rajchinagundi7498
@rajchinagundi7498 9 ай бұрын
Doesnt make a differnce if recursive stack overflows@@CrabGuyy
@s016_aviratshambharkar2
@s016_aviratshambharkar2 9 ай бұрын
Subarrays should be n (n + 1) / 2 right ??
@ahmedbenromdhane-q9s
@ahmedbenromdhane-q9s 9 ай бұрын
there are n(n+1)/2 sub arrays not n²
@kartikhegde533
@kartikhegde533 9 ай бұрын
he probably mentioned about overall complexity. which is still n^2
@pdjeowudjx
@pdjeowudjx 9 ай бұрын
i was waiting thx
@Logeshwar-s7m
@Logeshwar-s7m 9 ай бұрын
could you also upload videos for leetcode biweekly contests
@akialter
@akialter 9 ай бұрын
I just solved this and the video uploaded 😅. Still watching tho, I like your explanation
@krishnakanthati8510
@krishnakanthati8510 9 ай бұрын
How did you solve this?
@shellingford5534
@shellingford5534 9 ай бұрын
I still don't understand why we are doing j + 1 in the else portion. Can someone please explain this to me like I am 5...
@anti-tankartur677
@anti-tankartur677 9 ай бұрын
Basically, else is only done when the stack is empty. If the stack is empty after popping the last element, that means it is the smallest number in that array upto THAT index, which means that it is going yo be present in every subarray and will also be the minimum of all these subarrays. For example, suppose the stack is empty and the element popped is 1 at the index of 2. At index 0 and 1, you have 3 and 2. So for all the subarrays from the index 0 to 2, 1 is going to be the minimum nunber and hence j+1 (2+1 =3 ) as 3 subarrays will have the minimum as 1. Hope this helps.
@ducthinh2412
@ducthinh2412 9 ай бұрын
Let's say we have: nums = [2, 3, 5, 1] index = [0, 1, 2, 3] Let's say we are currently at index 3 (value = 1). Our stack (index, value) is: stack = [(0,2), (1,3), (2,5)] Since 1 is less than all of the values in the stack, we pop everything from the stack. When we get to (0,2), the top of the stack, the right count is 3. For the left count, since the stack is now empty, there is only a single value from the beginning of the array till this point, which is 2. Its index is 0, hence we need to add 1 to the index to get the count of subarrays from the beginning up to and including 2
@AdenGolden
@AdenGolden 9 ай бұрын
+ 1 is include the jth element itself if the stack is empty is 0 + 1(itself) = 1
@JosephMuturi-j4d
@JosephMuturi-j4d 4 ай бұрын
@@anti-tankartur677 This is an amazing explanation,,,,,only few can understand how figuring that out almost solves the problem,,,even neetcode couldn't explain that one,,,,it's genius
@jamjam3448
@jamjam3448 5 ай бұрын
but total number of subarrays is n*(n+1)/2 instead of n^2.
@harshitsharma2639
@harshitsharma2639 4 ай бұрын
thats order n^2 tho
@jamjam3448
@jamjam3448 4 ай бұрын
@@harshitsharma2639 You're talking of complexity, not the number of subarrays. They are different
@harshitsharma2639
@harshitsharma2639 4 ай бұрын
@@jamjam3448 i know that dude. The time to traverse and build the result will still be O(n^2) thats what neet was trying to say.
@jamjam3448
@jamjam3448 4 ай бұрын
@@harshitsharma2639 yeah i think that's what he was trying to say also but he kept saying number of times instead of the time complexity as the two are different.
@randomisedstrength5050
@randomisedstrength5050 9 ай бұрын
I didn't understand anything related to the use of stack in the code 😶‍🌫
@ehm-wg8pd
@ehm-wg8pd 4 ай бұрын
if you get this interview question, omaewa mou shindeiru
@pastori2672
@pastori2672 9 ай бұрын
too much intuition
@haoli8983
@haoli8983 4 ай бұрын
this question is so hard == why just medium ?
@Moch117
@Moch117 9 ай бұрын
This question made me question Leetcode smh Did you solve it on your own
@vinsin4619
@vinsin4619 9 ай бұрын
can you explain the last code
@vinsin4619
@vinsin4619 9 ай бұрын
the negative inf added to front and back of the array
@harryliu799
@harryliu799 9 ай бұрын
The neg inf at the back ensures that the elements in the monotonic increasing stack are processed, as everything inside is smaller than neg inf (same as the original loop over the stack).@@vinsin4619
@aaditya_87
@aaditya_87 5 ай бұрын
hey man , its time for u to answer here why u did that
@sumitrohilla1494
@sumitrohilla1494 6 ай бұрын
how can I continue watching this video, when 1 min in you are giving wrong explaination.... no. of subarrays are not n^2 its n(n+1)/2
@anandp7482
@anandp7482 5 ай бұрын
its O(n ^ 2) . n * (n + 1) /2 is still O (n ^ 2)
@sumitrohilla1494
@sumitrohilla1494 5 ай бұрын
Ohh, sry for the wrong explanation, I am not talking about time complexity.. He said no. of subarrays is array are n^2..but no of subarrays are n(n+1)/2
@eyesgotshowyo7800
@eyesgotshowyo7800 6 ай бұрын
i understood nothing
@shreehari2589
@shreehari2589 9 ай бұрын
Def hard not med
@rishujeetrai5780
@rishujeetrai5780 3 ай бұрын
😭👍
@johnthompson1327
@johnthompson1327 9 ай бұрын
first
@jaatharsh
@jaatharsh 9 ай бұрын
checking solution in Python is useless for understanding, when iterating ur iterating from top of stock to bottom or reverse. Python is such a sloppy choice of language for DSA
@hehehehehe2003
@hehehehehe2003 7 ай бұрын
still dont get it
Making an Algorithm Faster
30:08
NeetCodeIO
Рет қаралды 139 М.
Maximum XOR for Each Query - Leetcode 1829 - Python
11:35
NeetCodeIO
Рет қаралды 2,9 М.
Osman Kalyoncu Sonu Üzücü Saddest Videos Dream Engine 275 #shorts
00:29
風船をキャッチしろ!🎈 Balloon catch Challenges
00:57
はじめしゃちょー(hajime)
Рет қаралды 35 МЛН
Triple kill😹
00:18
GG Animation
Рет қаралды 18 МЛН
They Chose Kindness Over Abuse in Their Team #shorts
00:20
I migliori trucchetti di Fabiosa
Рет қаралды 11 МЛН
How I would learn Leetcode if I could start over
18:03
NeetCodeIO
Рет қаралды 658 М.
Continuous Subarray Sum - Leetcode 523 - Python
14:56
NeetCode
Рет қаралды 70 М.
Minimum Falling Path Sum - Leetcode 931 - Python
14:02
NeetCodeIO
Рет қаралды 14 М.
How I Approach a New Leetcode Problem (live problem solving)
25:31
Minimum Size Subarray Sum - Leetcode 209 - Python
12:30
NeetCode
Рет қаралды 93 М.
My Brain after 569 Leetcode Problems
7:50
NeetCode
Рет қаралды 2,7 МЛН
Contiguous Array - Leetcode 525 - Python
15:41
NeetCodeIO
Рет қаралды 28 М.
Osman Kalyoncu Sonu Üzücü Saddest Videos Dream Engine 275 #shorts
00:29