Hey striver, for the following test case Input: intervals = [[1,3], [4,5], [6,7], [8,10]], newInterval = [5,6]; the above code might give an error a very small change in your code is this insertInterval(intervals, newInterval) { // Your code here let n=intervals.length; let res=[]; let i=0; while(i
We can use binary search to find the overlapping region. The remaining left and right parts have just been added without any modification. The time complexity remains the same but just a slight optimization.
small recomendations in the code: 1. use different variables to find the starting and ending ranges for intersection values 2. use a = in the 2nd while to take in the range when the newInterval[1] matches the intervals[i][1] in any case, for eg: newInterval={4,8} and the one of the intervals is [.......{8,10},.....] code: vector insert(vector& intervals, vector& newInterval) { vectorans; int i=0; while(i
@cs_in_10_minutes both are not same.. intervalEnd value is changing but not newinterval[1]. You have to update the value in each comparison. So you need to use intervalEnd
for java class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { ArrayList ans = new ArrayList(); int start= 0; int end= 1; int n = intervals.length; int i = 0; //left part which do not have overlap while(i
Here is the smaller code: class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { int n = intervals.length; List ans = new LinkedList(); int i =0; while(i
This could have been done with binary search as well. Thats the point of this question otherwise what's the difference in this question and merge intervals. Could have just added the new interval into the old and applied merge intervals ?
struct Range { int start; int end; }; class Solution { static bool comparator(const Range &a, const Range &b) { return a.start < b.start; } public: vector insert(vector& intervals, vector& newInterval) { int n = intervals.size(); Range arr[n + 1];
for (int i = 0; i < n; i++) { arr[i].start = intervals[i][0]; arr[i].end = intervals[i][1]; }
JAVA SOLUTION 👇 class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { ArrayList ans = new ArrayList(); int n = intervals.length; int i = 0;
// Add all intervals before the new interval while (i < n && intervals[i][1] < newInterval[0]) { ArrayList temp = new ArrayList(); temp.add(intervals[i][0]); temp.add(intervals[i][1]); ans.add(temp); i++; }
// Merge overlapping intervals with the new interval while (i < n && intervals[i][0]
May be you can identify where to insert newInterval into given intervals using binary search after that you can use merge interval problem solution.(No need to sort in merge interval problem solution) Time complexity:O(logn) + O(n).
when I saw this question, there was in my mind that it is saying to insert, ofcourse it will be inplace and end up doing inplace which beats 5% people in runtime😂 BUT beats 98% people in terms of Memory Here is the code, if anyone wanna see this approach class Solution { public: vector insert(vector& inter, vector& newinter) { int n=inter.size(),low=0,high=n-1,ans=-11; while(low
while(i
CORRECTION : In the 2nd while loop initialization it will be while(i < n && intervals[i][0]
Yess
Hey striver, for the following test case Input: intervals = [[1,3], [4,5], [6,7], [8,10]], newInterval = [5,6]; the above code might give an error a very small change in your code is this insertInterval(intervals, newInterval) {
// Your code here
let n=intervals.length;
let res=[];
let i=0;
while(i
We can use binary search to find the overlapping region. The remaining left and right parts have just been added without any modification. The time complexity remains the same but just a slight optimization.
small recomendations in the code:
1. use different variables to find the starting and ending ranges for intersection values
2. use a = in the 2nd while to take in the range when the newInterval[1] matches the intervals[i][1] in any case, for eg: newInterval={4,8} and the one of the intervals is [.......{8,10},.....]
code:
vector insert(vector& intervals, vector& newInterval) {
vectorans;
int i=0;
while(i
It would give wrong output. Inside the second while loop condition should be i
@@anoopkumaryadav5084 both are same buddy
@cs_in_10_minutes both are not same.. intervalEnd value is changing but not newinterval[1]. You have to update the value in each comparison. So you need to use intervalEnd
Thank you so much for great Explaination.
for java
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
ArrayList ans = new ArrayList();
int start= 0;
int end= 1;
int n = intervals.length;
int i = 0;
//left part which do not have overlap
while(i
Here is the smaller code:
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int n = intervals.length;
List ans = new LinkedList();
int i =0;
while(i
class Solution {
public:
vector insert(vector& intervals, vector& newInterval) {
int n = intervals.size();
int i = 0;
vectorresult;
while(i
old videos were better
what if i just take the new interval as input, then sort it, and the find the overlapping part and fix it using min and max?
sorting will increase time complexity to nlogn
we can do binary search
This could have been done with binary search as well.
Thats the point of this question otherwise what's the difference in this question and merge intervals.
Could have just added the new interval into the old and applied merge intervals ?
CPP
class Solution {
public:
vector insertNewEvent(int n, vector &intervals, vector &newEvent)
{
vector ans;
int i = 0;
while(i < n && intervals[i][1] < newEvent[0])
{
ans.push_back(intervals[i]);
i++;
}
// int start = -1
while(i < n && intervals[i][0] newEvent[1])
{
ans.push_back(intervals[i]);
i++;
}
return ans;
}
};
UNDERSTOOD;
Sir please start making videos on strings and stacks
struct Range {
int start;
int end;
};
class Solution {
static bool comparator(const Range &a, const Range &b) {
return a.start < b.start;
}
public:
vector insert(vector& intervals, vector& newInterval) {
int n = intervals.size();
Range arr[n + 1];
for (int i = 0; i < n; i++) {
arr[i].start = intervals[i][0];
arr[i].end = intervals[i][1];
}
arr[n].start = newInterval[0];
arr[n].end = newInterval[1];
sort(arr, arr + n + 1, comparator);
vector ans;
ans.push_back({arr[0].start, arr[0].end});
for (int i = 1; i < n + 1; i++) {
vector& last = ans.back();
if (arr[i].start > last[1]) {
ans.push_back({arr[i].start, arr[i].end});
} else {
last[1] = max(last[1], arr[i].end);
}
}
return ans;
}
};
class Solution {
public:
vector insert(vector& intervals, vector& newInterval) {
int n = intervals.size();
vector ans;
intervals.push_back(newInterval);
sort(intervals.begin(),intervals.end());
ans.push_back(intervals[0]);
for (int i = 1; i last[1]) {
ans.push_back(intervals[i]);
} else {
last[1] = max(last[1], intervals[i][1]);
}
}
return ans;
}
};
in the last question (1,2) & (2,3) were not considered as overlapping but in this one it will considered, how can we be sure ?
can't we use a modified version of binary search ??
We could use binary search to find the middle portion, right?
Yes it is optimal, but still the algorithm will be O(n) only
solved after a couple of wrong answers unfortunately:
bool comp(vector & a, vector &b){
if(a[0] == b[0])
return a[1] < b[1];
return a[0] < b[0];
}
class Solution {
public:
vector insert(vector& intervals, vector& newInterval){
if(intervals.empty())
return {newInterval};
if(newInterval.empty())
return intervals;
if(newInterval[1] < intervals[0][0]){
intervals.push_back(newInterval);
sort(intervals.begin(), intervals.end(), comp);
return intervals;
}
if(newInterval[0] > intervals[intervals.size()-1][1]){
intervals.push_back(newInterval);
sort(intervals.begin(), intervals.end(), comp);
return intervals;
}
vector ans;
int i = 0;
while(i < intervals.size() && (intervals[i][1] < newInterval[0])){
ans.push_back({intervals[i]});
i++;
}
int j = intervals.size() - 1;
while(j >=0 && (intervals[j][0] > newInterval[1])){
ans.push_back({intervals[j]});
j--;
}
int start = min(intervals[i][0], newInterval[0]);
int end = max(intervals[j][1],newInterval[1]);
ans.push_back({start, end});
sort(ans.begin(), ans.end(), comp);
return ans;
}
};
notes link is not a correct one for code
thank you
JAVA SOLUTION 👇
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
ArrayList ans = new ArrayList();
int n = intervals.length;
int i = 0;
// Add all intervals before the new interval
while (i < n && intervals[i][1] < newInterval[0]) {
ArrayList temp = new ArrayList();
temp.add(intervals[i][0]);
temp.add(intervals[i][1]);
ans.add(temp);
i++;
}
// Merge overlapping intervals with the new interval
while (i < n && intervals[i][0]
super simple
class Solution {
public:
vector insert(vector& intervals, vector& newInterval) {
intervals.push_back(newInterval);
sort(intervals.begin(),intervals.end());
int n=intervals.size();
vectorans;
for(int i=0;ians.back()[1])
ans.push_back(intervals[i]);
else
ans.back()[1]=max(ans.back()[1],intervals[i][1]);
}
return ans;
}
};
given intervals are already sorted, use it rather than sorting it again and converting this question into merge intervals!
@@anubhav0355Look carefully this is converted into merge interval question
this is an nlogn approach, will give TLE, we need O(n). And yeah as it is already sorted we shouldn't sort again
@@psinity However it is accepted
May be you can identify where to insert newInterval into given intervals using binary search after that you can use merge interval problem solution.(No need to sort in merge interval problem solution)
Time complexity:O(logn) + O(n).
⚠ mistake in 2nd while loop -> use
Best explaination for perticular problem
when I saw this question, there was in my mind that it is saying to insert, ofcourse it will be inplace and end up doing inplace which beats 5% people in runtime😂 BUT beats 98% people in terms of Memory
Here is the code, if anyone wanna see this approach
class Solution {
public:
vector insert(vector& inter, vector& newinter) {
int n=inter.size(),low=0,high=n-1,ans=-11;
while(low
bro are u able to understand your code now
@@iamnottech8918 lol I mean still know what intuition I took and code again, but not the exact code
tysm sir
phenomenal playlist
understood
Understood
nice
very well explained playlist
super simple code
class Solution {
public:
vector insert(vector& intervals, vector& newInterval) {
intervals.push_back(newInterval);
sort(intervals.begin(),intervals.end());
int n=intervals.size();
vectorans;
for(int i=0;ians.back()[1])
ans.push_back(intervals[i]);
else
ans.back()[1]=max(ans.back()[1],intervals[i][1]);
}
return ans;
}
};
watched
Thank you
Understood