Coding

Insert Interval

Asked at

Expedia

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a 2D array Intervals, where Intervals[i] = [start[i], end[i]] represents the start and end of the ith interval, the array represents non-overlapping intervals sorted in ascending order by start[i].

Given another array newInterval, where newInterval = [start, end] represents the start and end of another interval, merge newInterval into Intervals such that Intervals remain non-overlapping and sorted in ascending order by start[i].

Return Intervals after the insertion of newInterval.

Input : Intervals = [ [1, 3] , [6, 9] ] , newInterval = [2, 5]

Output : [ [1, 5] , [6, 9] ]

Explanation : After inserting the newInterval the Intervals array becomes [ [1, 3] , [2, 5] , [6, 9] ]. So to make them non overlapping we can merge the intervals [1, 3] and [2, 5]. So the Intervals array is [ [1, 5] , [6, 9] ].

Input : Intervals = [ [1, 2] , [3, 5] , [6, 7] , [8,10] ] , newInterval = [4, 8]

Output : [ [1, 2] , [3, 10] ]

Explanation : The Intervals array after inserting newInterval is [ [1, 2] , [3, 5] , [4, 8] , [6, 7] , [8, 10] ]. We merge the required intervals to make it non overlapping. So final array is [ [1, 2] , [3, 10] ].

Input : Intervals = [ [1, 2] , [3, 5] , [6, 7] , [8,10] ] , newInterval = [1, 8]

0 <= Intervals.length <= 105
0 <= start[i] < end[i] <= 107
0 <= start < end <= 107
Intervals[i].length = 2
newInterval.length = 2

cpp

class Solution {
public:
    vector<vector<int>> insertNewInterval(vector<vector<int>>& Intervals, vector<int>& newInterval){
        //your code goes here
    }
};

java

class Solution {
    public int[][] insertNewInterval(int[][] Intervals, int[] newInterval) {
        //your code goes here
    }
}

python

class Solution:
    def insertNewInterval(self, Intervals, newInterval):
        #your code goes here

javascript

class Solution {
    insertNewInterval(Intervals, newInterval) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public List<int[]> insertNewInterval(List<int[]> Intervals, int[] newInterval)
    {
        //your code goes here
    }
}

func insertNewInterval(intervals [][]int, newInterval []int) [][]int {
	//your code goes here
}

Stuck? Show a way to structure it+

01Confirm ordering and endpoint convention
02Append intervals strictly before new interval
03Expand new bounds across all overlaps
04Append merged result then untouched suffix

Reference answer

Start by restating the input contract for Insert Interval and testing the smallest boundary case before choosing the algorithm. Assuming non-overlapping intervals sorted by start, copy intervals ending before the new interval, merge every interval that overlaps it, then append the merged interval and the remaining suffix. Overlap uses start <= currentEnd under closed interval semantics. Explain the invariant while coding, then show how each update preserves it. One pass over the intervals is O(n) time and building the returned list is O(n) space. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How would you insert into unsorted intervals?
Tests: follow-up reasoning
What changes for half-open intervals?
Tests: constraint adaptation

Hiring now

Expedia has 109 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Development Engineer III - Platform Productivity Tools
India - Gurgaon
Sr Manager, Software Engineering
Austin Domain 11 - HomeAway
Software Development Engineer II
India - Gurgaon

Or practice this question first

Next question