the time complexity is worst. As example n = 2. [0,100000000],[0,100000000]. The time would be O(n*m), where m is 100000000 m= avg range of start to end. Simply, using an boolean array or Set would also get me O(n*M) solution.
@MinhNguyen-lz1pg2 жыл бұрын
Love the approach! Just a quick comment on his optimization and why does this help with the run time. Let's take the in-problem example with additional paint job: paint = [[1,4],[4,7],[5,8],[5, 10]]. With his optimization, after going thru the first 3 paint intervals, we already paint from 1->8. For the last interval, we got ask a paint job from 5->10, then we move from 5 to 8 (instead of 7, then have to call 7->8 again) - which save loop calls
@sharathkumar15762 жыл бұрын
Thanks a lot. Your videos make me feel like I'm stepping closer to Google my dream company. Keep making these videos 😀😀. Not even my classmates helped me during college but you are doing it. Thanks a lot man you are God 💞
@crackfaang2 жыл бұрын
Lots more Google videos coming soon. But not gonna lie Google is the number # 1 dickhead company when it comes to asking totally bullshit questions. So much dynamic programming and you already know we don't solve that shit on this channel. Hard to find questions that are popular yet can be solved with a sane approach lol
@sharathkumar15762 жыл бұрын
@@crackfaang no issues brother. I'll try to solve whatever u do and make a note of it and repeat once again. Even if I'm able to crack Amazon or any other faang I'm really greatful. I just want to prove to myself that I can. A year before I always thought this was impossible.
@keerthivasan95482 жыл бұрын
@@crackfaang bro leetcode 862
@yunaf46092 жыл бұрын
Great explanation! this problem really had me stumped from the discuss section, but your explanation was excellent. Thanks for making this.
@jataman1232 жыл бұрын
Thanks for this explanation. I implemented it in a similar way, but it fails one last performance test. Can you spot any mistakes? class Solution: def amountPainted(self, paint: List[List[int]]) -> List[int]: ranges = {} worklog = [] for start, stop in paint: count = 0 p = start while p < stop: if p in ranges: p = ranges[p] else: ranges[p] = stop count += 1 p += 1 worklog.append(count) return worklog
@tsaregrad2 жыл бұрын
How this is better than the suggested solution in hints? Still N^2 for time. And for space it's actually O(5 * 10^4) for space
@agnilasmagicland96722 жыл бұрын
Very clever. Thank you for the solution.
@keerthivasan95482 жыл бұрын
Is Sorting by start time and overlapping intervals kind of solution works?
@roywastaken Жыл бұрын
make more videos bro, you're underrated af
@subee128 Жыл бұрын
Thank you so much
@laughwithme46583 ай бұрын
so this is a DSU approach, how can someone come with this approach in interview, that's way out of my league, although after knowing the approach it's sounds easy
@crackfaang3 ай бұрын
You need to have seen the questions before... or have 200 IQ. Easier to do the former lol