RANGE MODULE | LEETCODE 715 | PYTHON SOLUTION

Problem Link: leetcode.com/problems/range-m...
Discord Link: / discord
This this video we are solving, or should I say re-solving a popular Google interview question: Range Module (Leetcode 715).
This problem is just hard. No way around it. I can see why Google asks this. It's quite a horrendous question and the optimal solution is not something you'll figure out with a 200 IQ. Nonetheless, we are solving it today and hopefully this video helps!
TIMESTAMPS
00:00 Intro
00:30 Example
02:42 Add Range Intuition
06:13 Remove Range Intuition
10:56 Query Range Intuition
14:50 Coding
26:05 Time/Space Complexity
29:00 Outro

[@yantinglai7183]

Thank you so much for making these videos! I have been using your channel to prepare for the Google interviews. I feel your frustrations and I this make me feel I am not alone. Google interview questions are not easy, but trying to learn a little bit more day by day is important!

[@GiridharaSaiPavanKumarGurram]

how did it go?

[@umeshhbhat]

I had tried solving it with the BST. It was pain in the ass, so many edge cases. Asking this question in a interview should be an offense!

[@viniciusalves9927]

"Unfortunately, I don't have the 200 IQ to understand the Segment Tree solution" was perfect hahahahaha

[@ahmedtremo]

Great Explanation, thanks!

[@stith_pragya]

Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@niyatikhandelwal7017]

Very well explained!

[@ziqinwu2337]

Thank you so much!

[@apoorvwatsky]

Actually this is a perfect candidate for a segment tree with range updates using lazy propagation. If the constraints were around 1e5 or 1e6 it'd be much easier, you probably wouldn't even have to worry about anything but range updates. But it can go up to 1e9 so you've got to be clever with it. Anyway that's what I'm gonna try out. It'll probably take up my day but it's worth it.

[@crackfaang]

Yea I took one look at the segment tree solutions and two thoughts came to mind: 1). I have no fucking idea what is going on here 2). There’s no way I’m going to be able to explain this coherently even if I do get a clue how the code works 😂

[@apoorvwatsky]

@@crackfaang yea that's another topic on its own. Segment tree is a prerequisite for it. You can still do point updates in log(n) time, but for this problem there's no way around it, it'd just be nlog(n). Lazy propagation solves this in logarithmic time. First time when I learned about it, I couldn't fucking believe it. Range updates in log(n)? Get the fk outta here! xD

[@lavanyam3224]

​@@apoorvwatsky were you able to write a solution using segment trees?

[@lalitvinde1441]

hey can you make solution of it using segment tree Data structure for better optimisation ?

[@crackfaang]

No sorry won't be remaking the video. The segment tree is way overkill here. There should be solutions on LC with the code for that if that's specifically what you are after. I generally try to go for more human understandable solutions. When the optimal is something crazy like some wild DP, segment tree, fenwick tree... I never bother because that's just some bullshit and most people won't understand it (probably me included lol)

[@akakartiksaini]

Really well explained man!!

[@crackfaang]

Glad you liked the video! Make sure to subscribe if you haven't already

[@akakartiksaini]

@@crackfaang sub from 1k🔥

[@azeemansari3517]

Getting a type error with the line of code index = bisect.bisect(self.intervals, [left, int(1e9)])

[@precisionchoker]

Thanks

[@crackfaang]

No problem, hope the video was helpful for you

[@WoWUndad]

[@aaditya_87]

shhaata

[@sharathkumar8338]

Hi I have one doubt. there is this codecamp called scaler academy. They charge 274000 indian rupees (around 3320.07 USD todays' exchange rate). I had logged in to their website for free OS course. Right now their sales team is reaching out to me saying we'll teach you DSA and full stack engineering and guide you in internship grade projects and they have tie ups with 750 companies for jobs and on their website they have posted salaries of their alumnis after they enrolled for their bootcamp. Do you think it is worth it. They are calling me like everyday.

[@crackfaang]

I personally find boot camps to be a total waste of money and time. Everything you need to know is online for free. All it comes down to is do you have the discipline and work ethic to make it happen or do you need some boot camp to hold your hand through it? And think about who will be teaching you? Are any of these people worthwhile learning from? Most of the time they’ll sell you a dream and let your brain think up some scenario where after 12 weeks you’ll now have a Google job. It doesn’t work that way, there are no hacks, there are no shortcuts. It’s your money and you’re free to do with it as you please but if it were me I’d block their number and save my money.

[@sharathkumar8338]

@@crackfaang well they say mentors will be from FAANG types of companies 😅. and could be sidehustle for those SWE's.

[@aishwariyaaish8305]

U can try S30 ds and algo class to master in dsa which is just $799

[@sharathkumar8338]

@@aishwariyaaish8305 what is that?

[@aishwariyaaish8305]

@@sharathkumar8338 its a 4 months class taken by an Indian in USA, my frnds tried that class and feedback was so good. just try googling s30, they will check your knowledge in any coding by taking a small interview, if you clear that they will admit you for their course. But every penny is worth the course.