#57 Insert Interval
the problem
In plain words
intervals is sorted by start and has no overlaps. Insert newInterval, merging wherever needed, and return the result, still sorted and with no overlaps.
in intervals = [[1,3],[6,9]], newInterval = [2,5]
out [[1,5],[6,9]]
in intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
out [[1,2],[3,10],[12,16]]
[4,8] overlaps [3,5], [6,7] and [8,10].
- 0 ≤ intervals.length ≤ 10⁴
- Sorted by start, non-overlapping
- 0 ≤ start ≤ end ≤ 10⁵
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternInterval merging (sort by start)
The list splits into three runs: intervals entirely before the new one, intervals that overlap it, and intervals entirely after it. Copy, absorb, copy.
solutions
From brute force to optimal
Add the new interval and run Merge Intervals.
- Add newInterval to the list.
- Sort by start.
- Merge as in LC 56.
It re-sorts, ignoring that the input was already sorted.
The new list.
class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> all = new ArrayList<>(Arrays.asList(intervals)); all.add(newInterval); all.sort((a, b) -> Integer.compare(a[0], b[0])); // re-sort everything List<int[]> merged = new ArrayList<>(); for (int[] iv : all) { // then plain Merge Intervals if (merged.isEmpty() || iv[0] > merged.get(merged.size() - 1)[1]) { merged.add(new int[] {iv[0], iv[1]}); } else { int[] last = merged.get(merged.size() - 1); last[1] = Math.max(last[1], iv[1]); } } return merged.toArray(new int[0][]); }}Copy intervals that end before the new start. Absorb intervals that start at or before the new end. Copy the rest.
- While intervals[i][1] < start: copy.
- While intervals[i][0] ≤ end: grow [start, end] to cover it.
- Add [start, end]; copy the remainder.
Each interval is visited once.
The output list.
class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> out = new ArrayList<>(); int i = 0, n = intervals.length; int start = newInterval[0], end = newInterval[1]; while (i < n && intervals[i][1] < start) { // 1. ends before the new one starts out.add(intervals[i++]); } while (i < n && intervals[i][0] <= end) { // 2. overlaps: absorb it start = Math.min(start, intervals[i][0]); end = Math.max(end, intervals[i][1]); i++; } out.add(new int[] {start, end}); while (i < n) out.add(intervals[i++]); // 3. starts after the new one ends return out.toArray(new int[0][]); }}Dry run
in the room
How to say it in the interview
talk track
- Point out that the input is sorted, so a re-sort wastes time. Then describe the three phases.
- Test an empty list, an insert at the front or back, and an insert that swallows everything.
traps
- Using
<=in phase 1. Then [1,5] and [5,7] would not merge, though touching should. - Forgetting to add the merged interval when the absorb phase finds nothing to absorb.
what they ask next
Follow-ups
Binary search instead?
You can find both boundaries in O(log n), but building the output is still O(n).
before you submit
Edge cases to test
- Empty list → just [newInterval].
- The new interval touches a neighbour, [[1,5]] + [5,7] → [[1,7]].
- The new interval swallows everything → one interval.
- The new interval lands in a gap and touches nothing → it is simply placed between.
practise next
Similar problems
- #56Merge IntervalsMediumin Intervals
- #228Summary RangesEasyin Intervals