Insert Interval | Brute Force | Optimal | Google | Apple | codestorywithMIK

This is our 32nd Video on our Array Playlist.
In this video we will try to solve a very very popular and good Qn "Insert Interval".
Interval Based Qns are often asked by Google.

We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Insert Interval
Company Tags : Google, Twitter, Microsoft, Apple, Amazon

0:00 - Intro
0:33 - Understand Qn
4:08 - Brute Force
12:25 - Live Coding Brute Force
16:14 - Optimal
21:44 - Live Coding Optimal

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[OtakRajCodes]

Thanks for the wonderful explanation!!
For my fellow new leetcoder's
struggling with java solution, here is the code with same logic :

class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res = new ArrayList<>();
if(intervals.length<=0){
res.add(newInterval);
return res.toArray( new int[res.size()][]);
}
//iterate over given interval array
boolean isUsed= false;
for(int []interval : intervals ){
//if starting([0]) index of current interval is greater than ending
//index([1])of newInterval
// that means we have found the point where new interval belongs
// insert first the newinterval and then current interval and make isUsed true
if(!isUsed && interval[0]>newInterval[1]){
res.add(newInterval);
res.add(interval);
isUsed =true;
} else if(!isUsed && interval[1]>=newInterval[0]){
//modify the newIndex if overlap is found
newInterval[0] = Math.min(interval[0], newInterval[0]);
newInterval[1] = Math.max(interval[1], newInterval[1]);
}else{
//if current interval does not overlap with newInterval
res.add(interval);
}
}
//if the newinterval has not been inserted -> insert at the end.
if(!isUsed){
res.add(newInterval);

}
return res.toArray( new int[res.size()][]);

}
}

[ayusshrathore]

Where were you before? How come your channel isn't being recommended for such questions. On-point explanation. Thanks, man!
And, is it possible if you could code in java too? Would help a lot of viewers.

[shreyash__]

DAY - 8 16/02/2024

STARTED WITH LEC 32 .

[_utpallucky]

We can use stack as well na ??Jabvi hme prev chj ki jrrt pre aap ne hi btaya tha mtlb we can think of stack too❤️.

[Irin]

i submitted the 1st approach of brute force, it gets accepted without showing tle on leetcode

[Raj-wxfi]

sir ek chij samjh nhi ayi ki optimal solution me agar end me jo bache hai wo sb daal de rhe ans me to agar aage koi interval merge krne wala hua to wo to bach gaya fir??

[girikgarg]

class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> res;
int n = intervals.size(), i = 0;
while(i < n && intervals[i][1] < newInterval[0])
while(i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
++i;
}
res.push_back(newInterval);
while(i < n)
return res;
}
};

Approach based on finding the correct sorted position for the interval and merging the next intervals further

[adityatripathi]

i was having problem in how to tell whether the intervals are overlapping or not ..but now its clear🙌

[philosphize]

Thanks, Bruteforce solution is also submitted successfully

[udaytewary]

You are really great bhaiya just loved your way of explanation and you won't believe that I was also thinking about the same solution of using an array but don't having clear idea how to proceed further but after watching you I got clear how to proceed further.

One doubt bhaiya in your first approach where you were erasing element in that for while loop you write i< intervals.size instead of n I am not able to understand that part can you please explain that

And also wanted to ask one thing bhaiya I have never seen this question and while solving the optimise approach of using array comes to my mind is it good or bad for interview perspective

[piyushacharya]

Bro, I could also code it up but I used for loop so my code was failing all the test cases. but now I know the reason.😅😅

[turing_machine]

Thanks Bhaiya for wonderful explanation..

[jyotishmoydeka]

Bhaiya thora sa arrows need to burst ballons wale ke type hoga na? and wonderfull explanantion as usual!!❤‍🔥❤‍🔥

[Krishna-mzuk]

.insert() method for arrays is available in c++
is there any similar method to inert() in array in java

[Raj]

More simple code to understand :-
vector<vector<int>> ans;
int i;

for( i = 0 ; i < intervals.size();i++)
{

int currstart = intervals[i][0];
int currend = intervals[i][1];

if(newinterval[1] < currstart) {
ans.push_back(newinterval);
ans.insert(ans.end(), intervals.begin(), intervals.end());
return ans;}

else if (newinterval[0] > currend )
{
ans.push_back(intervals[i]);
}
else
{

newinterval[0] = min( newinterval[0], currstart);
newinterval[1] = max(newinterval[1], currend);


}




}

ans.push_back(newinterval);

return ans;

[harshitrajput]

Solved myself after watching lecture 31
here is c++ code
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>>result;
int n = intervals.size();

sort(intervals.begin(), intervals.end());
vector<int>prev = intervals[0];
for(int i = 1;i<n+1;i++){
int curr_sp = intervals[i][0];
int curr_ep = intervals[i][1];
int prev_sp = prev[0];
int prev_ep = prev[1];
if(curr_sp>prev_ep){ // no overlap
result.push_back(prev);
prev = intervals[i];
}
else{
prev[0]= min(prev_sp, curr_sp);
prev[1] = max(prev_ep, curr_ep);
}

}
result.push_back(prev);
return result;
}
};
❤❤

[akashgoyal]

use good quality mike your sound is very low

[pritishpattnaik]

Apne ek interval wala problem solve karwaya tha, eie uske baad easy lag raha hai

[manojyadav]

Sir, How you are able to use this Leetcode UI, Beacause in my Windows Laptop it is changed and is very bad

[satyamkumaryadav]

bro can you upload a series on binary trees, like where you teach how to approach a problem