Insert Interval solution and explanation
Google
TCS
9 more videos on this problem
Insert Interval - Leetcode 57 - PythonNeetCode · 11:51 · 241K views
L9. Insert Intervals | Greedy Algorithms Playlisttake U forward · 13:16 · 140K views
Insert Interval (LeetCode 57) } Full solution with different scenariosNikhil Lohia · 20:14 · 10K views
57. Insert Interval | leetcode daily challenge | DSA | Shashwat Tiwari HindiShashCode · 18:24 · 7K views
[Java] Leetcode 57. Insert Interval [Intervals #2]Eric Programming · 11:26 · 7K views
Insert Intervals - LeetCode 57 - JavaScriptAlgoJS · 10:14 · 2K views
Leetcode - Insert Interval (Python)Timothy H Chang · 9:01 · 2K views
Insert Interval | LeetCode 57 (Medium)Destination FAANG · 19:25 · 976 views
57. Insert Interval | JavaScript | Simple Solution | O(n) Time Complexity | LeetCode Daily ChallengeLeetCodeWithMonu · 21:50 · 913 views
57. Insert Interval | LeetCode | Java SolutionShrayansh Jain · 12:30 · 693 views
The problem
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.
Note that you don't need to modify intervals in-place. You can make a new array and return it.
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 <= 104intervals[i].length == 20 <= starti <= endi <= 105intervalsis sorted bystartiin ascending order.newInterval.length == 20 <= start <= end <= 105
Approach overview
Problem Overview: You’re given a list of non-overlapping intervals sorted by start time. Insert a new interval into the list and merge any overlaps so the final result remains sorted and non-overlapping.
Approach 1: Insert and Merge Intervals (O(n) time, O(n) space)
Iterate through the intervals and build the result list while handling three cases: intervals completely before the new interval, overlapping intervals, and intervals completely after it. First append all intervals whose end is smaller than newInterval[0]. Next merge overlaps by updating newInterval using start = min(start, interval[0]) and end = max(end, interval[1]). Once merging is complete, append the merged interval and then append the remaining intervals. This works because the input is already sorted, so overlapping intervals appear consecutively. Time complexity is O(n) since you scan the list once, and space complexity is O(n) for the output array. This is a classic pattern for interval problems built on simple iteration over an array.
Approach 2: Binary Search for Insert Position then Merge (O(n) time, O(1)-O(n) space)
Instead of scanning from the start, use binary search to find the first interval whose start time is greater than or equal to the new interval’s start. This gives the insertion position in O(log n). Insert the interval at that index, then perform a standard merge pass over the list to combine overlaps. The merge step still takes O(n), so the overall complexity remains O(n). This method is useful when you frequently insert intervals into a large sorted list because locating the insertion point becomes faster. It combines searching techniques from binary search with the standard interval merging pattern.
Recommended for interviews: The single-pass insert-and-merge approach is what interviewers expect. It shows that you recognize the sorted property and can merge intervals efficiently in one traversal. The binary search variant demonstrates deeper understanding of optimizing insertion, but the straightforward O(n) merge approach is usually considered the cleanest and most practical solution.
Approach 1: Approach 1: Insert and Merge Intervals
In this approach, we'll first identify where the new interval should be inserted to maintain order. After insertion, we'll iterate over the array and merge overlapping intervals.
def insert(intervals, newInterval):
result = []
i = 0
while i < len(intervals) and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
while i < len(intervals) and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
while i < len(intervals):
result.append(intervals[i])
i += 1
return resultimport java.util.ArrayList;
import java.util.List;
public class IntervalInsertion {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0])
result.add(intervals[i++]);
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.add(newInterval);
while (i < intervals.length)
result.add(intervals[i++]);
return result.toArray(new int[result.size()][]);
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> result;
size_t i = 0;
while (i < intervals.size() && intervals[i][1] < newInterval[0])
result.push_back(intervals[i++]);
while (i < intervals.size() && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i++;
}
result.push_back(newInterval);
while (i < intervals.size())
result.push_back(intervals[i++]);
return result;
}const insert = (intervals, newInterval) => {
const result = [];
let i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0])
result.push(intervals[i++]);
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
while (i < intervals.length)
result.push(intervals[i++]);
return result;
};#include <stdio.h>
#include <stdlib.h>
struct Interval {
int start;
int end;
};
struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) {
struct Interval* result = malloc(sizeof(struct Interval) * (intervalsSize + 1));
int i, j = 0;
for (i = 0; i < intervalsSize && intervals[i].end < newInterval.start; ++i) {
result[j++] = intervals[i];
}
for (; i < intervalsSize && intervals[i].start <= newInterval.end; ++i) {
newInterval.start = fmin(newInterval.start, intervals[i].start);
newInterval.end = fmax(newInterval.end, intervals[i].end);
}
result[j++] = newInterval;
while (i < intervalsSize) {
result[j++] = intervals[i++];
}
*returnSize = j;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[][] Insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new List<int[]>();
int i = 0;
while (i < intervals.Length && intervals[i][1] < newInterval[0])
result.Add(intervals[i++]);
while (i < intervals.Length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.Min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.Max(newInterval[1], intervals[i][1]);
i++;
}
result.Add(newInterval);
while (i < intervals.Length)
result.Add(intervals[i++]);
return result.ToArray();
}
}The Python solution leverages the dynamic nature of lists. It loops through the given intervals and processes them based on their relation to the new interval, producing a merged list of intervals.
Time Complexity: O(n) for merging intervals.
Space Complexity: O(n) due to the result list.
Approach 2: Approach 2: Binary Search for Insert Position then Merge
This approach optimizes finding the insert position using binary search. After inserting the new interval, it merges overlapping intervals. This is slightly more efficient when the intervals list is large.
def insert(intervals, newInterval):
def find_position(arr, target):
low, high = 0, len(arr)
while low < high:
mid = (low + high) // 2
if arr[mid][0] < target:
low = mid + 1
else:
high = mid
return low
pos = find_position(intervals, newInterval[0])
intervals.insert(pos, newInterval)
merged = [intervals[0]]
for i in range(1, len(intervals)):
if merged[-1][1] >= intervals[i][0]:
merged[-1][1] = max(merged[-1][1], intervals[i][1])
else:
merged.append(intervals[i])
return mergedimport java.util.ArrayList;
import java.util.List;
public class IntervalInsertion {
public int[][] insert(int[][] intervals, int[] newInterval) {
int pos = binarySearchPosition(intervals, newInterval[0]);
int[][] newIntervals = new int[intervals.length + 1][2];
System.arraycopy(intervals, 0, newIntervals, 0, pos);
newIntervals[pos] = newInterval;
System.arraycopy(intervals, pos, newIntervals, pos + 1, intervals.length - pos);
List<int[]> merged = new ArrayList<>();
merged.add(newIntervals[0]);
for (int i = 1; i < newIntervals.length; i++) {
int[] last = merged.get(merged.size() - 1);
if (last[1] < newIntervals[i][0])
merged.add(newIntervals[i]);
else
last[1] = Math.max(last[1], newIntervals[i][1]);
}
return merged.toArray(new int[merged.size()][]);
}
private int binarySearchPosition(int[][] intervals, int start) {
int low = 0, high = intervals.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (intervals[mid][0] < start)
low = mid + 1;
else
high = mid;
}
return low;
}
}#include <vector>
#include <algorithm>
using namespace std;
int findPosition(const vector<vector<int>>& intervals, int start) {
int low = 0, high = intervals.size();
while (low < high) {
int mid = low + (high - low) / 2;
if (intervals[mid][0] < start)
low = mid + 1;
else
high = mid;
}
return low;
}
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int pos = findPosition(intervals, newInterval[0]);
intervals.insert(intervals.begin() + pos, newInterval);
vector<vector<int>> result = {intervals[0]};
for (int i = 1; i < intervals.size(); ++i) {
if (result.back()[1] < intervals[i][0])
result.push_back(intervals[i]);
else
result.back()[1] = max(result.back()[1], intervals[i][1]);
}
return result;
}function insert(intervals, newInterval) {
function findInsertPosition(arr, target) {
let low = 0, high = arr.length;
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (arr[mid][0] < target) low = mid + 1;
else high = mid;
}
return low;
}
const pos = findInsertPosition(intervals, newInterval[0]);
intervals.splice(pos, 0, newInterval);
const result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = result[result.length - 1];
if (last[1] >= intervals[i][0])
last[1] = Math.max(last[1], intervals[i][1]);
else
result.push(intervals[i]);
}
return result;
}#include <stdio.h>
#include <stdlib.h>
int binarySearch(int** intervals, int size, int target) {
int low = 0, high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (intervals[mid][0] == target)
return mid;
else if (intervals[mid][0] < target)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
int** insert(int** intervals, int intervalsSize, int* newInterval, int newIntervalSize, int* returnSize) {
int pos = binarySearch(intervals, intervalsSize, newInterval[0]);
int** result = (int**)malloc(sizeof(int*) * (intervalsSize + 1));
int k = 0;
for (int i = 0; i < pos; i++) {
result[k] = (int*)malloc(sizeof(int) * 2);
result[k][0] = intervals[i][0];
result[k++][1] = intervals[i][1];
}
int* mergedInterval = malloc(sizeof(int) * 2);
mergedInterval[0] = newInterval[0];
mergedInterval[1] = newInterval[1];
while (pos < intervalsSize && intervals[pos][0] <= mergedInterval[1]) {
mergedInterval[0] = fmin(mergedInterval[0], intervals[pos][0]);
mergedInterval[1] = fmax(mergedInterval[1], intervals[pos][1]);
pos++;
}
result[k++] = mergedInterval;
while (pos < intervalsSize) {
result[k] = (int*)malloc(sizeof(int) * 2);
result[k][0] = intervals[pos][0];
result[k++][1] = intervals[pos][1];
pos++;
}
*returnSize = k;
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[][] Insert(int[][] intervals, int[] newInterval) {
int insertPosition = BinarySearch(intervals, newInterval[0]);
List<int[]> newIntervals = new List<int[]>(intervals);
newIntervals.Insert(insertPosition, newInterval);
List<int[]> mergedIntervals = new List<int[]> { newIntervals[0] };
for (int i = 1; i < newIntervals.Count; i++) {
var lastInterval = mergedIntervals[mergedIntervals.Count - 1];
if (lastInterval[1] >= newIntervals[i][0])
lastInterval[1] = Math.Max(lastInterval[1], newIntervals[i][1]);
else
mergedIntervals.Add(newIntervals[i]);
}
return mergedIntervals.ToArray();
}
private int BinarySearch(int[][] intervals, int start) {
int low = 0, high = intervals.Length;
while (low < high) {
int mid = (low + high) / 2;
if (intervals[mid][0] < start)
low = mid + 1;
else
high = mid;
}
return low;
}
}The Python approach combines binary search for efficient insertion with a concise method for merging intervals by positioning and combining correctly pre-sorted intervals quickly.
Time Complexity: O(n), dominated by the merge process post-binary search.
Space Complexity: O(n), exemplified by list handling for results.
Approach 3: Sorting + Interval Merging
We can first add the new interval newInterval to the interval list intervals, and then merge according to the regular method of interval merging.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of intervals.
function insert(intervals: number[][], newInterval: number[]): number[][] {
const merge = (intervals: number[][]): number[][] => {
intervals.sort((a, b) => a[0] - b[0]);
const ans: number[][] = [intervals[0]];
for (let i = 1; i < intervals.length; ++i) {
if (ans.at(-1)[1] < intervals[i][0]) {
ans.push(intervals[i]);
} else {
ans.at(-1)[1] = Math.max(ans.at(-1)[1], intervals[i][1]);
}
}
return ans;
};
intervals.push(newInterval);
return merge(intervals);
}func insert(intervals [][]int, newInterval []int) [][]int {
merge := func(intervals [][]int) (ans [][]int) {
sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
ans = append(ans, intervals[0])
for _, e := range intervals[1:] {
if ans[len(ans)-1][1] < e[0] {
ans = append(ans, e)
} else {
ans[len(ans)-1][1] = max(ans[len(ans)-1][1], e[1])
}
}
return
}
intervals = append(intervals, newInterval)
return merge(intervals)
}impl Solution {
pub fn insert(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> {
let mut merged_intervals = intervals.clone();
merged_intervals.push(vec![new_interval[0], new_interval[1]]);
// sort by elem[0]
merged_intervals.sort_by_key(|elem| elem[0]);
// merge interval
let mut result = vec![];
for interval in merged_intervals {
if result.is_empty() {
result.push(interval);
continue;
}
let last_elem = result.last_mut().unwrap();
if interval[0] > last_elem[1] {
result.push(interval);
} else {
last_elem[1] = last_elem[1].max(interval[1]);
}
}
result
}
}Approach 4: One-pass Traversal
We can traverse the interval list intervals, let the current interval be interval, and there are three situations for each interval:
- The current interval is on the right side of the new interval, that is,
newInterval[1] < interval[0]. At this time, if the new interval has not been added, then add the new interval to the answer, and then add the current interval to the answer. - The current interval is on the left side of the new interval, that is,
interval[1] < newInterval[0]. At this time, add the current interval to the answer. - Otherwise, it means that the current interval and the new interval intersect. We take the minimum of the left endpoint of the current interval and the left endpoint of the new interval, and the maximum of the right endpoint of the current interval and the right endpoint of the new interval, as the left and right endpoints of the new interval, and then continue to traverse the interval list.
After the traversal, if the new interval has not been added, then add the new interval to the answer.
The time complexity is O(n), where n is the number of intervals. Ignoring the space consumption of the answer array, the space complexity is O(1).
function insert(intervals: number[][], newInterval: number[]): number[][] {
let [st, ed] = newInterval;
const ans: number[][] = [];
let insert = false;
for (const [s, e] of intervals) {
if (ed < s) {
if (!insert) {
ans.push([st, ed]);
insert = true;
}
ans.push([s, e]);
} else if (e < st) {
ans.push([s, e]);
} else {
st = Math.min(st, s);
ed = Math.max(ed, e);
}
}
if (!insert) {
ans.push([st, ed]);
}
return ans;
}func insert(intervals [][]int, newInterval []int) (ans [][]int) {
st, ed := newInterval[0], newInterval[1]
insert := false
for _, interval := range intervals {
s, e := interval[0], interval[1]
if ed < s {
if !insert {
ans = append(ans, []int{st, ed})
insert = true
}
ans = append(ans, interval)
} else if e < st {
ans = append(ans, interval)
} else {
st = min(st, s)
ed = max(ed, e)
}
}
if !insert {
ans = append(ans, []int{st, ed})
}
return
}impl Solution {
pub fn insert(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> {
let mut inserted = false;
let mut result = vec![];
let (mut start, mut end) = (new_interval[0], new_interval[1]);
for iter in intervals.iter() {
let (cur_st, cur_ed) = (iter[0], iter[1]);
if cur_ed < start {
result.push(vec![cur_st, cur_ed]);
} else if cur_st > end {
if !inserted {
inserted = true;
result.push(vec![start, end]);
}
result.push(vec![cur_st, cur_ed]);
} else {
start = std::cmp::min(start, cur_st);
end = std::cmp::max(end, cur_ed);
}
}
if !inserted {
result.push(vec![start, end]);
}
result
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Insert and Merge Intervals | Time Complexity: O(n) for merging intervals. |
| Approach 2: Binary Search for Insert Position then Merge | Time Complexity: O(n), dominated by the merge process post-binary search. |
| Sorting + Interval Merging | – |
| One-pass Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Insert and Merge Intervals | O(n) | O(n) | Standard interview solution when intervals are already sorted and non-overlapping |
| Binary Search Insert then Merge | O(n) | O(1)-O(n) | Useful when repeatedly inserting into a large sorted interval list and you want faster index lookup |
Frequently asked questions
Is Insert Interval easy or hard?
Insert Interval is usually classified as a Medium difficulty problem. The logic is straightforward once you recognize the interval merging pattern, but handling edge cases like full containment or merging multiple overlapping intervals can make it tricky for beginners.
How to solve Insert Interval in O(n)?
Traverse the intervals and divide them into three groups: intervals that end before the new interval, intervals that overlap with it, and intervals that start after it. Merge overlaps by expanding the new interval’s start and end boundaries. Append the merged interval and then add the remaining intervals. This single pass guarantees O(n) time.
What is the best approach for Insert Interval?
The most common solution scans the array once and merges overlaps while inserting the new interval. Because the intervals are already sorted by start time, overlapping intervals appear consecutively, allowing a single pass. This insert-and-merge technique runs in O(n) time and O(n) space and is the approach most interviewers expect.
Is Insert Interval asked at Google/Amazon/Meta?
Insert Interval is a classic interval manipulation problem frequently reported in interviews at companies like Google, Amazon, Meta, and Microsoft. It tests understanding of interval merging, edge cases with overlaps, and efficient linear traversal of sorted arrays.
What data structure is used in Insert Interval?
The problem mainly uses arrays or lists to store intervals. The algorithm relies on sequential traversal and conditional merging of intervals rather than advanced data structures, though binary search may be used to locate the insertion index in a sorted array.
What is the time complexity of Insert Interval?
The optimal solution runs in O(n) time because each interval is processed at most once during the merge process. Even if you use binary search to find the insertion index in O(log n), the merge step still requires scanning the list, so the total complexity remains O(n).
Insert Interval Python or Java solution approach?
Both Python and Java implementations typically follow the same pattern: iterate through the interval list, append non-overlapping intervals before the new interval, merge overlapping ones by adjusting boundaries, then append the rest. The logic stays identical across languages with O(n) time complexity.