Merge Overlapping Intervals | Brute, Optimal with Precise TC analysis
Vložit
- čas přidán 30. 06. 2024
- Problem Link: bit.ly/3ItlwtJ
Notes/C++/Java/Python codes: takeuforward.org/data-structu...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
0:00 Introduction of Course
00:41 Problem Statement
01:15 Overlapping example
03:27 Brute force
03:56 approach
09:39 Code
13:30 Complexity
16:22 Optimal approach
16:38 Intuition
18:55 Code
21:36 Complexity
Please watch our new video on the same topic: czcams.com/video/IexN60k62jo/video.html
ye kya recurrsion chala rahe ho bhaiya 👀
Do give us a like if you understood everything, it won't cost you much :)
Hey Bro! 🎉 Your Graph and DP series is absolutely fantastic! 👌 Your content is top-notch and stands out from the rest. I've been searching everywhere, and your quality is unmatched. 😍
I do have a humble request - could you consider creating a compact playlist on Digit DP? Lately, I've encountered several LeetCode contests with questions related to Digit DP, and I'm struggling to crack them. I'm sure many of us are in the same boat. 💡
If you're on board with the idea of adding videos on DIGIT DP, please show your support by giving this comment a thumbs up! 👍 Let's learn and grow together. 📚💪
This is the first question where I took 1hr to understand the Brute force & 10 min to understand the Optimal logic 🙂
22 min ka to vvideo he lodu
@@tot7997 Comment parke samajna ka dimak bhi chahihe chomu
@@Akash-yr2if thoda humor bhi chahiye ig
coz both are the same... I mean he just decreases the complexity from O(2*n) to O(n) and for Java it didn't even do that bcoz we have to convert a list to an array at the end, So it remains O(2*n)
no problem bro we are playing with logic we don't take seriously to converting languages complexity
@@user-je7tz6le4k
understanding of brute force took me more time than understanding of optimal
To make his video in his regular pattern he intentionally adds unnecessary solutions and calls them brute force..
I generally do not comment even on good videos, but after watching this video, i really wanna say amazing explanation. You made a difficult problem easy. Excellent clarity of concept. Striver, you are the best💯
One of the greatest free course that I ever seen in CZcams
By Liking , We also tell you tube algorithm that provide us with such content instead of distracting useless videos!!!
When i understood this, I started liking every quality content videos and my recommendation is now really good.
Understood!
I was able to build up the logic but could not code it by myself...
Waiting for that magic to happen when i can code even listening to music
you make this question so easy to be understood by your proper explanation .🔥🔥 really thanks a lot
Understood! Super amazing explanation as always, thank you so so much for your effort!!
i am glad i was able to think of optimal solution directly and didnt even realised it was optimal. Felt like
Brute Force was more tougher than the optimal one. LOL
nice bro but how? through practice ?
@@sayamparejiya1510 yes brother... i have solved like 700 problems on CF and 400 + on GFG and Codechef combined.... so it takes alot of practice. but yeah number of questions doesnt matter... Good questions matter which teach you something that you can carry to 10 next questions
@@deathigniter2155 Thank for sharing.
I think my code is more intuitive (atleast to me) rather than the code you shown.(both approaches are same) (also I am not complaining, I am sharing this so that others can also share their opinion on mine). Below is my code:
#include
/*
intervals[i][0] = start point of i'th interval
intervals[i][1] = finish point of i'th interval
*/
vector mergeIntervals(vector &intervals)
{
int n = intervals.size();
sort(begin(intervals), end(intervals));
vector ans;
int i = 1;
int start = intervals[0][0], end = intervals[0][1];
while(i
bro........ i just write same code but little different...........
vector ans;
int n=arr.size();
int lastf=-1,lasts=-1;
for(int i=0;i=first)
{
lastf=min(lastf,first);
lasts=max(lasts,second);
}
else{
vector temp;
temp.push_back(lastf);
temp.push_back(lasts);
ans.push_back(temp);
lastf=first;
lasts=second;
}
}
else{
lastf=first;
lasts=second;
}
}
vector temp;
temp.push_back(lastf);
temp.push_back(lasts);
ans.push_back(temp);
return ans;
Two videos in a day ✅
It was so easy code at the end!! Thanks Striver.
bhaiya u re inspiration to all thrown ones like us thank u get a lot hope from u
Thank you sir for providing such great content ❤
This man deserves a salute!
Couldn't thank you enough sir!!
You are the savior
00:41 Problem Statement
01:15 Overlapping example
03:27 Brute force
03:56 approach
09:39 Code
13:30 Complexity
16:22 Optimal approach
16:38 Intuition
18:55 Code
21:36 Complexity
amazing explanation always worth watching your videos
That's really easy to understable. Thankyou
Man i have always been scared of arrays especially but after going through this sheet gradually my confidence is increasing. This is such a good resource for learning DSA. Thanks a lot striver bro for making this :)
i just want to say ,thank you thank you very much ..❤
Thank you for your wonderful explanation. Understood🙂
Thnk you, its helpful for me! to understand this concept very well.
So beautifully explained.
as usuall u jus made the problem loook easy bruh!!!!
was watching this tutorial on your website before after watching the video I came here to just like and comment on this video to tell how beautiful the explanation was loved it striver bhaiya❤❤
Understood Bro
Thank You for Upskilling us.
understood ,thnx for the amazing expplanation ❤❤❤❤👌👌
Very nice explanation!👏👏
Best Explanation bhaiya thanks a lot 🙏
Excellent explanation
Thank you so much 🎉 sir
Inspiration 🙏🏽🙏🏽
Thank you! Understood!
🤩🤩 Thank you Raj Bhaiya...
thank you sir , very nicely explained😊
Great Explanation Sir
Understood, thank you.
Understood, amazing coding , love it.
Understood Sir...........Enjoyed this lec...........
Great work raj.
awesome explanation bhaiya
Amazing!
The approaches you have taught in this video, 60-70% both the approaches come in my mind but i was struggling to implement it. Thank you very much bhaiya for this video! You are always a great tutor for me and everyone ❤❤
Thank you bro this is good teaching
Understood🔥
when I see your video i thought why we don't get this type of teacher in our engineering college .... i think 1.5 st years is enough to crack any coding interview .....💖💖💖💖💖💖❤❤❤❤❤❤❤❤
Nice explanation
A little change in the code (although striver's code is shorter) by updating the end every time we move to the next index:
vector overlappedInterval(vector& intervals) {
// Code here
sort(intervals.begin() , intervals.end());
vector ans;
int start = intervals[0][0];
int end = intervals[0][1];
for(int i = 1; i
Understood and I even made the algorithm myself before watching solution but wasnt able to write the code
Understood✅🔥🔥
Thankyou @TUF 😮
Thank You😄
Thanks a lot Bhaiya
Understood ❤❤
i was able to do the optimal solution on my own , feeling good 😌
I thought of the same brute force approach (with O(nlogn) time) after much thought but I didnt know u can sort 2d vector like that.
Understood 🎉
Understood❤
Understood!
What a ques but apart from this what a explenation😊
understood!. great as always. btw @striver the brute force code on the website is same for cpp and js (js code has been given in cpp as well ) kindly correct it.
I usually don't write comment but I think this time I should. Amazing explanation Sir. Thank You
UNDERSTOOD
Amazing
we can do it O(1) also in space, by checking the next element if it is overlapped we just change the current elements [1] element with max, than we just remove the [i+1] from the array and in the end we will have just our answer
understood 🤠
amazing
I'm still hustling, but this feeling is good
u r awsome sir:)
Just want to ask how to remember so many optimal approaches and what to do if a question comes in an interview which I have never seen before?
Comes with practice, you will get used to it.
true . great
Understood.
love you striver :)
So Instead of making a new int[][] ans. We can use the same given array to store answer. Which can potentially reduce the usage of extra space for storing answer.
understood
Python Code 🐍
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
ans = []
intervals.sort()
ans.append(intervals[0])
for i in intervals:
start = i[0]
end = i[1]
if start
Brute force approach would be O(N^2) like you pick every element and loop over others on the right?
awesome
Awesome
Please maintain consistency brother
Understood
There is an edge case, if ans.back()[0] > arr[I][0] you can put ans.back()[0] = min(ans.back()[0],arr[i][0]); in else part
instead of continue,if we just i++,will the tc remain same?
Striver ke itne saare DSA ke videos dekh liye, ab soch kar hi ajeeb lagta hai ki bhaiya kisi zamane me CP karte the....😅
Bro, is it normal to come up with optimal solution intuition without bruteforce because, sometimes whenever a question comes up the first solution that sometimes comes up is optimal. It is sometimes hard for me to come up with bruteforce
It is okay, but if you know solutions before hand, and you don't want to tell to the interviewer, drive the interview..
Can one of the solutions be using a set? We mark all the numbers within intervals in a set ranging from smallest number to the largest number in the array. Then we iterate over the set and select the consecutive numbers as one interval?
brute force seems to be more complex than the optimize one :)....btw superb content
what will be approach if it asks for subsets not subarrays
Where can I find the java solution?
Can you make a video on word break problem
18:33 "I am inside you" - Striver
what is meant by ans.back()? what does it do?
I was able to make the intutuion but was unable to convert it to code . :(
bhaiya , please add a feature in website where we can mark question for revisiting
We will soon
How do you know that your solution is the most optimal,I also thought this answer but I felt sorting is not required
Isn't this question somewut similar to the taps required to water a garden question from leetcode?
❤
what is the line ans.back()[1] reffer to?
how the time complexity of brute force will be o(2*n) bcz it O(n^2)