Merge Intervals | Leetcode | Problem-6 | Brute-Optimal | C++/Java

In case you are thinking to buy courses, please check below:

#dsa #course #placements

[takeUforward]

How is the new thumbnail, should we keep it for all ?
As always, if you understand, make sure you drop "understood" in the comment section, if you have doubt, drop that in, will revert :)
.

[sandeepnallala]

you are not striver, you are SAVIOUR : ) love ur lectures brother : )

[paridhijain]

this video is so well explained and I got each and every point of it. Referring Striver sheet along with this video. Thank you striver for making such wonderful content for us.

[GaneshBhutekar-nugd]

i did the same thing without any tutorial now i am feeling confident

[vaibhavyadav]

You don't know how much you're helping God bless you brother....

[aditya-blxh]

Want to be as dedicated as he is, he got a job then also he's helping us, great! Thank you so much bro

[nivedithat]

After watching video halfway through, I thought how lucky the current 2nd years and 3rd years are… they can watch the entire playlist in 10 days and voila!!! ready for cracking companies

[gouravmallick]

this was the most efficient explanation, thanks, sir.

[tanmaychandra]

Great effort Man we can learn alot from you there are several people who keep their all learnings within themselves but you came out and kept on sharing your knowledge . Great respect man.

[araragikoyomi]

I solved the brute force using graph by creating components of intervals which are overlapping and finding minimum and maximum range and insert it in the ans

[viggicodes]

I disable ad blocker and watch your videos. Keep up the good work striver !!

[vamshikrishnareddy]

also can be solved by using prefix sum, array between (1, and max), considering edge cases and space

[vishalm]

I think the brute force approach doesn't require sorting at all and would have time complexity O(n^2). First, we merge all the interval pairs that overlap and add to an array and form a result. Then we do it recursively to find if there's still some more merging possible and if not return the result. But surprisingly this algorithm is faster than the optimal solution mentioned.

LeetCode result : Runtime: 2 ms, faster than 99.47% of Java online submissions for Merge Intervals.

This is the version I implemented :-
public int[][] merge(int[][] intervals) {
int n = intervals.length;
boolean included[] = new boolean[n];
ArrayList<ArrayList<Integer>> arr = new
for(int i = 0;i<n;i++){
if(!included[i]){
included[i] = true;
int min = intervals[i][0];
int max = intervals[i][1];
for(int j = i+1;j<n;j++){
int min1 = intervals[j][0];
int max1= intervals[j][1];
if(!included[j] && Math.min(min, min1)<=Math.min(max, max1) && Math.max(min, min1) <=Math.max(max, max1)
&& Math.min(max, max1)>=Math.max(min, min1))
{
min = Math.min(min, min1);
max = Math.max(max, max1);
included[j] = true;
}
}
ArrayList<Integer> curr = new ArrayList();
curr.add(min);
curr.add(max);
arr.add(curr);
}
}
int res[][] = new int[arr.size()][2];
for(int i = 0;i<arr.size();i++){
res[i][0] = arr.get(i).get(0);
res[i][1] = arr.get(i).get(1);
}
if(intervals.length == res.length)
return res;
return merge(res);
}


Any improvements are always welcomed :)

[nishantmohanty]

Bhai apana bahut bhala kama karuchanti. Apana bahut bhala teacher.

[subhamkumar]

Explanation is extremely understandable and convenient:)

[annawilson]

we are comparing the first interval with itself, can avoid it. O/w, great job!

[Aditya-karn]

What you are doing is fabulous. I understand every concept that you are teaching. Can you make a video on Closest Palindrome problem, as i don't find any satisfactory video of this problem.

[pirangitharun]

I write my codes in java
and I came to know many new things after seeing your code. Thank you bro

[amarjeetkumarsingh]

This is your best explanation I have ever seen

[arup_creations]

We can also perform the optimised approach in-place. For each merge operation that we perform we can keep a count. We can update the interval 2D vector with the optimal intervals that we get instead of using mergeIntervals. Then we can return the interval from interval.begin() to interval.begin() + count - 1. This way the space complexity will further reduce to O(1).

Please let me know your views in this appeoach of mine.