  # Insert Interval

## Problem statement

You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [starti, endi]` represent the start and the end of the `ith` interval and `intervals` is sorted in ascending order by `starti`. You are also given an interval `newInterval = [start, end]` that represents the start and end of another interval.

Insert `newInterval` into `intervals` such that `intervals` is still sorted in ascending order by `starti` and `intervals` still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return `intervals` after the insertion.

Problem statement taken from: https://leetcode.com/problems/insert-interval.

Example 1:

``````Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output: [[1, 5], [6, 9]]
``````

Example 2:

``````Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]
Explanation: Because the new interval [4, 8] overlaps with [3, 5], [6, 7], [8, 10].
``````

Constraints:

``````- 0 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= starti <= endi <= 10^5
- intervals is sorted by starti in ascending order.
- newInterval.length == 2
- 0 <= start <= end <= 10^5
``````

### Solutions for Insert Interval

#### Approach 1: Handle all cases

When working on these kinds of problems, we first consider all the cases we need to handle when inserting a new interval. Here are the five cases we need to handle in our code:

Let's assume the new interval that gets inserted is [a, b].

1. Case 1: b < start value of first interval in list Insert the interval at the beginning of the list.

2. Case 2: end value of last interval in list < a Insert the interval at the end of the list

3. Case 3: a < (start value of first interval) and b > (end value of last interval) The new interval is a superset of this list. It contains all the intervals of the list. We return the new interval as a result.

4. Case 4: The new interval falls in between any two intervals in the list and is not overlapping with any interval We simply insert the interval in the correct position in the list. For eg.,

``````Input: List : [23, 46], [49, 65], [100, 120]
New interval : [70, 89]
Output: [23, 46], [49, 65], [70, 89], [100, 120]
``````
5. Case 5: When new interval overlaps with the intervals of the list We merge the new interval with overlapping intervals. To understand this case, please refer to the previous blog Merge Intervals.

A C++ snippet of this approach is as follows:

``````vector<vector<int>> insertNewInterval (vector<vector<int>>& intervals, interval newInterval) {
vector<vector<int>> result;
int n = intervals.size();

// if the set is empty, then simply insert newInterval and return.
if (n == 0) {
result.push_back(newInterval);
return result;
}

// case 1 and case 2 (new interval is not overlapping with any interval)
if (newInterval < intervals || newInterval > intervals[n - 1]) {
if (newInterval < intervals)
result.push_back(newInterval);

for (int i = 0; i < n; i++)
result.push_back(intervals[i]);

if (newInterval > intervals[n - 1])
result.push_back(newInterval);

return result;
}

// case 3 (New interval covers all existing)
if (newInterval <= intervals && newInterval >= intervals[n - 1]) {
result.push_back(newInterval);
return result;
}

// case 4 and case 5
// Two cases need to check whether intervals overlap or not.
bool overlap = true;

for (int i = 0; i < n; i++) {
overlap = doesOverlap(intervals[i], newInterval);
if (!overlap) {
result.push_back(intervals[i]);

// case 4
if (i < n && newInterval > intervals[i] && newInterval < intervals[i + 1])
result.push_back(newInterval);

continue;
}

// case 5: Merge Overlapping intervals.
vector<int> temp;
temp = min(newInterval, intervals[i]);

// Traverse the set until intervals are overlapping
while (i < n && overlap) {
// ending time of the newly merged interval is the maximum ending time of both
// overlapping intervals.
temp = max(newInterval, intervals[i]);

if (i == n - 1)
overlap = false;
else
overlap = doesOverlap(intervals[i + 1], newInterval);
i++;
}

i--;
result.push_back(temp);
}

return result;
}

bool doesOverlap(vector<int> a, vector<int> b) {
return (min(a, b) >= max(a, b));
}``````

The time complexity of this approach is O(n), and the space complexity is O(n).

#### Approach 2: Using Merge Intervals

As mentioned above, we can use the Merge Intervals approach to solve this problem.

We insert the new interval in the list and use the merge intervals solution.

A C++ snippet of this approach is as follows:

``````vector<vector<int>> merge(vector<vector<int>>& intervals, vector<int> newInterval) {
intervals.push_back(newInterval);
sort(intervals.begin(), intervals.end());

vector<vector<int>> result;

for(auto interval: intervals){
if(result.empty() || (result.back() < interval)){
result.push_back({interval, interval});
} else {
result.back() = max(result.back(), interval);
}
}

return result;
}``````

The time complexity of this approach is O(n * log n), because we are sorting the list. The space complexity is O(1).

#### Approach 3: Using Stack

We use stack to identify the interval in which it can be merged or placed at the correct position.

The C++ snippet of this approach is as follows:

``````vector<vector<int>> merge(vector<vector<int>>& intervals, vector<int> newInterval) {
stack< pair<int, int> > st;

// push the first interval to stack
st.push(intervals);

// store the top element of the stack
vector<int> top = st.top();

// Checking is newInterval is less than top
if (newInterval < top) {
// pop the top element as it will merge with the
// previous range
st.pop();

// re-assign top
top = min(top, newInterval);

// re-assign top
top = max(top, newInterval);

// push the current interval
st.push(top);
} else {
st.push(newInterval);
}

// iterate from i = 1 to n - 1
for (int i = 1; i < n; i++) {
// store the top element of the stack st
vector<int> top = st.top();

// if intervals[i] is less than top
if (intervals[i] < top) {
st.pop();

// re-assign top
top = min(top, intervals[i]);

// re-assign top
top = max(top, intervals[i]);

// push the current interval
st.push(top);
} else {
st.push(intervals[i]);
}
}

// storing the final intervals
stack<vector<vector<int>>> result;

// popping the stack elements
while (st.empty() != true) {
vector<int> element = st.top();
st.pop();

result.push(element);
}

return result;
}``````

The time complexity of this approach is O(n), and the space complexity is O(n).

#### Approach 4: Optimized solution without using additional space

We can solve this problem without using any additional space. In Approach 1, we handled five cases. We need to handle only cases 1 and 4 explicitly, and the rest of the cases can be handled in a single loop.

Let's check the algorithm first.

#### Algorithm

``````// set size of intervals array
- n = intervals.size()
i = 0

// iterate over the intervals list till the new interval start value is less than
// any of the interval's end values in the list
- loop while i < n && intervals[i] < newInterval

// keep adding the intervals to the final result
- result.push_back(intervals[i])

- increment i; i++
- end while

// once we find the correct slot, now loop till the new interval end value is greater than
// any of the interval's start values in the list
- loop while i < n && newInterval >= intervals[i]

// this code will handle the merging of the intervals based on
// new interval start and end values
// we also update the values of the new interval
- newInterval = min(newInterval, intervals[i])
- newInterval = max(newInterval, intervals[i])

- increment i; i++
- end while

// append the new interval to result
- result.push_back(newInterval)

// append the remaining intervals of the list to the result
- loop while i < n
- result.push_back(intervals[i])
- increment i; i++
- end while

- return result
``````

The time complexity of this approach is O(n), and the space complexity is O(1).

Check out our solutions in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int n = intervals.size(), i = 0;
vector<vector<int>> result;

while(i < n && intervals[i] < newInterval){
result.push_back(intervals[i]);
i++;
}

while(i < n && newInterval >= intervals[i]){
newInterval = min(newInterval, intervals[i]);
newInterval = max(newInterval, intervals[i]);
i++;
}

result.push_back(newInterval);

while(i < n){
result.push_back(intervals[i]);
i++;
}

return result;
}
};``````

#### Golang solution

``````func insert(intervals [][]int, newInterval []int) [][]int {
n, i := len(intervals), 0
var result [][]int

for i < n && intervals[i] < newInterval {
result = append(result, intervals[i])
i++
}

for i < n && newInterval >= intervals[i] {
newInterval = min(newInterval, intervals[i])
newInterval = max(newInterval, intervals[i])
i++
}

result = append(result, newInterval)

for i < n {
result = append(result, intervals[i])
i++
}

return result
}

func min(a, b int) int {
if a < b {
return a
}

return b
}

func max(a, b int) int {
if a > b {
return a
}

return b
}``````

#### JavaScript solution

``````/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function(intervals, newInterval) {
let n = intervals.length, i = 0;
let result = [];

while(i < n && intervals[i] < newInterval){
result.push(intervals[i]);
i++;
}

while(i < n && newInterval >= intervals[i]){
newInterval = Math.min(newInterval, intervals[i]);
newInterval = Math.max(newInterval, intervals[i]);
i++;
}

result.push(newInterval);

while(i < n){
result.push(intervals[i]);
i++;
}

return result;
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

``````Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]
newInterval = [4, 8]

Step 1: n = intervals.size()
= 5
i = 0
vector<vector<int>> result

Step 2: loop while i < n && intervals[i] < newInterval
0 < 5 && intervals < newInterval
true && 2 < 4
true

result.push_back(intervals[i])
result.push_back(intervals)
result.push_back([1, 2])
result = [[1, 2]]

i++
i = 1

loop while i < n && intervals[i] < newInterval
1 < 5 && intervals < newInterval
true && 5 < 4
false

Step 3: loop while i < n && newInterval >= intervals[i]
1 < 5 && newInterval >= intervals
true && 8 >= 3
true

newInterval = Math.min(newInterval, intervals[i])
= Math.min(newInterval, intervals)
= Math.min(4, 3)
= 3

newInterval = Math.max(newInterval, intervals[i])
= Math.max(newInterval, intervals)
= Math.max(8, 5)
= 8

newInterval = [3, 8]

i++
i = 2

loop while i < n && newInterval >= intervals[i]
2 < 5 && newInterval >= intervals
true && 8 >= 6
true

newInterval = Math.min(newInterval, intervals[i])
= Math.min(newInterval, intervals)
= Math.min(3, 6)
= 3

newInterval = Math.max(newInterval, intervals[i])
= Math.max(newInterval, intervals)
= Math.max(8, 7)
= 8

newInterval = [3, 8]

i++
i = 3

loop while i < n && newInterval >= intervals[i]
3 < 5 && newInterval >= intervals
true && 8 >= 8
true

newInterval = Math.min(newInterval, intervals[i])
= Math.min(newInterval, intervals)
= Math.min(3, 8)
= 3

newInterval = Math.max(newInterval, intervals[i])
= Math.max(newInterval, intervals)
= Math.max(8, 10)
= 10

newInterval = [3, 10]

i++
i = 4

loop while i < n && newInterval >= intervals[i]
4 < 5 && newInterval >= intervals
true && 8 >= 12
false

Step 4: result.push_back(newInterval)
result.push_back([3, 10])
result = [[1, 2], [3, 10]]

Step 5: loop while i < n
4 < 5
true

result.push_back(intervals[i])
result.push_back(intervals)
result.push_back([12, 16])
result = [[1, 2], [3, 10], [12, 16]]

i++
i = 5

loop while i < n
5 < 5
false

Step 6: return result

We return the answer as [[1, 2], [3, 10], [12, 16]].
``````