Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Given time intervals, merge all pairs of overlapping ones until no intervals overlap. Output should contain only mutually exclusive intervals.

All the intervals are closed intervals, i.e. the lower and upper limits are *inclusive*.

```
{
"intervals": [
[1, 3],
[5, 7],
[2, 4],
[6, 8]
}
```

Output:

```
[
[1, 4],
[5, 8]
]
```

[1, 3] and [2, 4] were overlapping, so they have been merged and became [1, 4].\ [5, 7] and [6, 8] have been merged and became [5, 8].

```
{
"intervals": [
[100, 154],
[13, 47],
[1, 5],
[2, 9],
[7, 11],
[51, 51],
[47, 50]
]
}
```

Output:

```
[
[1, 11],
[13, 50],
[51, 51],
[100, 154]
]
```

[1, 5] and [2, 9] have been merged and became [1, 9].\ [1, 9] and [7, 11] have been merged and became [1, 11].\ [13, 47] and [47, 50] have been merged and became [13, 50].\ [51, 51] and [100, 154] did not overlap with any others, so they were kept unchanged.

- Intervals in the input come in no particular order.
- Order of intervals in the output does not matter.

Constraints:

- 1 <= number of input intervals <= 10
^{5} - -10
^{9}<= lower limit of an interval <= upper limit of an interval <= 10^{9}

We provided three solutions.

A naive approach would be iterating over `intervals`

and checking if `intervals[i]`

is already removed.

- If it is, continue.
- If it is not, check if
`intervals[i]`

overlaps any other interval. If it overlaps k-th interval, remove the k-th interval and merge it into the current one.

For removing an interval, one way is to make the interval invalid (i.e. start > end).

O(n^{2}) where `n`

is length of `intervals`

.

O(1).

All updates are done in-place. No extra space is used.

O(n) where `n`

is length of `intervals`

.

```
/*
Asymptotic complexity in terms of the length of the given list \`n\`:
* Time: O(n ^ 2).
* Auxiliary space: O(1).
* Total space: O(n).
*/
static ArrayList<ArrayList<Integer>> get_merged_intervals(ArrayList<ArrayList<Integer>> intervals) {
for (int i = 0; i < intervals.size(); i++) {
// Check if it is an invalid interval
if (isInvalidInterval(intervals.get(i))) {
continue;
}
for (int j = 0; j < intervals.size(); j++) {
// Check if it is an invalid interval
if (i == j || isInvalidInterval(intervals.get(j))) {
continue;
}
// Check if interval[i] and interval[j] overlap.
if (isOverlapping(intervals.get(i), intervals.get(j))) {
intervals.get(i).set(0, Math.min(intervals.get(i).get(0), intervals.get(j).get(0)));
intervals.get(i).set(1, Math.max(intervals.get(i).get(1), intervals.get(j).get(1)));
invalidateInterval(intervals.get(j));
// To remove an interval from intervals, we make it invalid
// (i.e. interval.start > interval.end).
// Actually removing it from the array (and move all elements with larger indices)
// would be inefficient.
}
}
}
ArrayList<ArrayList<Integer>> outputArray = new ArrayList<>();;
for (int i = 0; i < intervals.size(); i++) {
if (!isInvalidInterval(intervals.get(i))) {
outputArray.add(intervals.get(i));
}
}
return outputArray;
}
private static boolean isInvalidInterval(ArrayList<Integer> intervals) {
return (intervals.get(0) > intervals.get(1));
}
private static void invalidateInterval(ArrayList<Integer> interval) {
interval.set(0, 1);
interval.set(1, 0);
}
private static boolean isOverlapping(ArrayList<Integer> interval1, ArrayList<Integer> interval2) {
return !isInvalidInterval(interval1) && !isInvalidInterval(interval2) &&
!(interval1.get(1) < interval2.get(0) || interval2.get(1) < interval1.get(0));
}
```

A more efficient approach.

Sort the input array of intervals in increasing order of the lower limit. Once we have sorted intervals, we can combine all intervals in a linear traversal.

Following is the detailed step by step algorithm.

- Sort the intervals based on increasing order of starting time.
- Push the first interval on to a stack.
- For each interval do the following
- If the current interval does not overlap with the stack top, push it.
- If the current interval overlaps with stack top and ending time of current interval is more than that of stack top, update stack top with the ending time of current interval.

- At the end stack contains the merged intervals.

O(n * log(n)) where `n`

is length of `intervals`

.

As we have to sort the interval array, followed by linear traversal, time complexity will be O(n * log(n)) + O(n) = O(n * log(n)).

O(n) where `n`

is length of `intervals`

.

Here we used a stack. So, auxiliary space used is O(n).

(We ignore the auxiliary space used by the built-in sort function that we use. Depending on implementation, library, language, it can be different.)

O(n) where `n`

is length of `intervals`

.

```
/*
Asymptotic complexity in terms of the length of the given list \`n\`:
* Time: O(n * log(n)).
* Auxiliary space: O(n).
* Total space: O(n).
*/
static ArrayList<ArrayList<Integer>> get_merged_intervals(ArrayList<ArrayList<Integer>> intervals) {
// Sorting the input interval array by their starting points in increasing order
Collections.sort(intervals, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> object1, ArrayList<Integer> object2) {
int x = object1.get(0) - object2.get(0);
if (x != 0) {
return x;
} else {
return object1.get(1) - object2.get(1);
}
}
});
Stack<ArrayList<Integer>> stack = new Stack<>();
ArrayList<Integer> popped;
for (ArrayList<Integer> interval : intervals) {
if (!stack.isEmpty()) {
// Check if interval at the top of the stack overlaps with current interval.
if (stack.peek().get(1) >= interval.get(0)) {
// Check if interval at the top of the stack has the upper limit lesser than
// that of the current interval.
if (stack.peek().get(1) < interval.get(1)) {
// Update ending point of interval at the top of the stack with that
// of the current interval.
popped = stack.pop();
popped.set(1, interval.get(1));
stack.push(popped);
}
} else {
// if not overlapping
stack.push(interval);
}
} else {
// if stack was empty i.e. it was the first interval
stack.push(interval);
}
}
return new ArrayList<>(stack);
}
```

Auxiliary space used in the above approach is O(n). It can be reduced.

The idea remains the same as discussed in the previous approach. Sort the interval array in the increasing order of the lower limit. Once you have sorted intervals, you can combine all intervals in a linear traversal.

Following is the detailed step by step algorithm:

Let `last`

be the last interval of non-overlapping intervals. `last`

= 0.

Iterating over `intervals`

, starting from second interval (1 <= `i`

<= `n`

- 1)

- Check if
`intervals[i]`

is overlapping with`intervals[last]`

- If overlapping, merge
`intervals[i]`

and`intervals[last]`

, then to merge them, it is sufficient to update only endpoint of`intervals[last]`

as it is guaranteed that the lower limit of`intervals[last]`

<= lower limit of`intervals[i][0]`

as the array is sorted by starting point. - If non-overlapping, we increment last and moving on,
`intervals[i]`

is the new interval under test of overlapping with following intervals.

- If overlapping, merge
- repeat step 1 for
`i`

=`i`

+ 1.

O(n * log(n)) where `n`

is length of `intervals`

.

As we have to sort the interval array, followed by linear traversal, time complexity will be O(n * log(n)) + O(n) = O(n * log(n)).

O(1).

All updates are done in-place. No extra space is used.

(We ignore the auxiliary space used by the built-in sort function that we use. Depending on implementation, library, language, it can be different.)

O(n) where `n`

is length of `intervals`

.

```
/*
Asymptotic complexity in terms of the length of the given list \`n\`:
* Time: O(n * log(n)).
* Auxiliary space: O(1).
* Total space: O(n).
*/
static ArrayList<ArrayList<Integer>> get_merged_intervals(ArrayList<ArrayList<Integer>> intervals) {
// Sorting the input interval array by their starting points in increasing order
Collections.sort(intervals, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> object1, ArrayList<Integer> object2) {
int x = object1.get(0) - object2.get(0);
if (x != 0) {
return x;
} else {
return object1.get(1) - object2.get(1);
}
}
});
int last = 0;
for (int i = 1; i < intervals.size(); i++) {
// Checking if intervals[last] and intervals[i] overlap.
if (intervals.get(last).get(1) >= intervals.get(i).get(0)) {
// If overlapping, then merge intervals[i] into intervals[last]
// For merging them, it is sufficient to update only endpoint of intervals[last] as
// it is guaranteed that intervals[last][0]<=intervals[i][0] , last<i
intervals.get(last).set(1, Math.max(intervals.get(last).get(1), intervals.get(i).get(1)));
} else {
// intervals[last] and intervals[i] are found non-overlapping.
// Moving on, intervals[i] is the new interval under test of overlapping with following intervals.
last++;
intervals.set(last, intervals.get(i));
}
}
return new ArrayList<>(intervals.subList(0, last + 1));
}
```

We hope that these solutions to merging overlapping intervals have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.

Given time intervals, merge all pairs of overlapping ones until no intervals overlap. Output should contain only mutually exclusive intervals.

All the intervals are closed intervals, i.e. the lower and upper limits are *inclusive*.

```
{
"intervals": [
[1, 3],
[5, 7],
[2, 4],
[6, 8]
}
```

Output:

```
[
[1, 4],
[5, 8]
]
```

[1, 3] and [2, 4] were overlapping, so they have been merged and became [1, 4].\ [5, 7] and [6, 8] have been merged and became [5, 8].

```
{
"intervals": [
[100, 154],
[13, 47],
[1, 5],
[2, 9],
[7, 11],
[51, 51],
[47, 50]
]
}
```

Output:

```
[
[1, 11],
[13, 50],
[51, 51],
[100, 154]
]
```

[1, 5] and [2, 9] have been merged and became [1, 9].\ [1, 9] and [7, 11] have been merged and became [1, 11].\ [13, 47] and [47, 50] have been merged and became [13, 50].\ [51, 51] and [100, 154] did not overlap with any others, so they were kept unchanged.

- Intervals in the input come in no particular order.
- Order of intervals in the output does not matter.

Constraints:

- 1 <= number of input intervals <= 10
^{5} - -10
^{9}<= lower limit of an interval <= upper limit of an interval <= 10^{9}

We provided three solutions.

A naive approach would be iterating over `intervals`

and checking if `intervals[i]`

is already removed.

- If it is, continue.
- If it is not, check if
`intervals[i]`

overlaps any other interval. If it overlaps k-th interval, remove the k-th interval and merge it into the current one.

For removing an interval, one way is to make the interval invalid (i.e. start > end).

O(n^{2}) where `n`

is length of `intervals`

.

O(1).

All updates are done in-place. No extra space is used.

O(n) where `n`

is length of `intervals`

.

```
/*
Asymptotic complexity in terms of the length of the given list \`n\`:
* Time: O(n ^ 2).
* Auxiliary space: O(1).
* Total space: O(n).
*/
static ArrayList<ArrayList<Integer>> get_merged_intervals(ArrayList<ArrayList<Integer>> intervals) {
for (int i = 0; i < intervals.size(); i++) {
// Check if it is an invalid interval
if (isInvalidInterval(intervals.get(i))) {
continue;
}
for (int j = 0; j < intervals.size(); j++) {
// Check if it is an invalid interval
if (i == j || isInvalidInterval(intervals.get(j))) {
continue;
}
// Check if interval[i] and interval[j] overlap.
if (isOverlapping(intervals.get(i), intervals.get(j))) {
intervals.get(i).set(0, Math.min(intervals.get(i).get(0), intervals.get(j).get(0)));
intervals.get(i).set(1, Math.max(intervals.get(i).get(1), intervals.get(j).get(1)));
invalidateInterval(intervals.get(j));
// To remove an interval from intervals, we make it invalid
// (i.e. interval.start > interval.end).
// Actually removing it from the array (and move all elements with larger indices)
// would be inefficient.
}
}
}
ArrayList<ArrayList<Integer>> outputArray = new ArrayList<>();;
for (int i = 0; i < intervals.size(); i++) {
if (!isInvalidInterval(intervals.get(i))) {
outputArray.add(intervals.get(i));
}
}
return outputArray;
}
private static boolean isInvalidInterval(ArrayList<Integer> intervals) {
return (intervals.get(0) > intervals.get(1));
}
private static void invalidateInterval(ArrayList<Integer> interval) {
interval.set(0, 1);
interval.set(1, 0);
}
private static boolean isOverlapping(ArrayList<Integer> interval1, ArrayList<Integer> interval2) {
return !isInvalidInterval(interval1) && !isInvalidInterval(interval2) &&
!(interval1.get(1) < interval2.get(0) || interval2.get(1) < interval1.get(0));
}
```

A more efficient approach.

Sort the input array of intervals in increasing order of the lower limit. Once we have sorted intervals, we can combine all intervals in a linear traversal.

Following is the detailed step by step algorithm.

- Sort the intervals based on increasing order of starting time.
- Push the first interval on to a stack.
- For each interval do the following
- If the current interval does not overlap with the stack top, push it.
- If the current interval overlaps with stack top and ending time of current interval is more than that of stack top, update stack top with the ending time of current interval.

- At the end stack contains the merged intervals.

O(n * log(n)) where `n`

is length of `intervals`

.

As we have to sort the interval array, followed by linear traversal, time complexity will be O(n * log(n)) + O(n) = O(n * log(n)).

O(n) where `n`

is length of `intervals`

.

Here we used a stack. So, auxiliary space used is O(n).

(We ignore the auxiliary space used by the built-in sort function that we use. Depending on implementation, library, language, it can be different.)

O(n) where `n`

is length of `intervals`

.

```
/*
Asymptotic complexity in terms of the length of the given list \`n\`:
* Time: O(n * log(n)).
* Auxiliary space: O(n).
* Total space: O(n).
*/
static ArrayList<ArrayList<Integer>> get_merged_intervals(ArrayList<ArrayList<Integer>> intervals) {
// Sorting the input interval array by their starting points in increasing order
Collections.sort(intervals, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> object1, ArrayList<Integer> object2) {
int x = object1.get(0) - object2.get(0);
if (x != 0) {
return x;
} else {
return object1.get(1) - object2.get(1);
}
}
});
Stack<ArrayList<Integer>> stack = new Stack<>();
ArrayList<Integer> popped;
for (ArrayList<Integer> interval : intervals) {
if (!stack.isEmpty()) {
// Check if interval at the top of the stack overlaps with current interval.
if (stack.peek().get(1) >= interval.get(0)) {
// Check if interval at the top of the stack has the upper limit lesser than
// that of the current interval.
if (stack.peek().get(1) < interval.get(1)) {
// Update ending point of interval at the top of the stack with that
// of the current interval.
popped = stack.pop();
popped.set(1, interval.get(1));
stack.push(popped);
}
} else {
// if not overlapping
stack.push(interval);
}
} else {
// if stack was empty i.e. it was the first interval
stack.push(interval);
}
}
return new ArrayList<>(stack);
}
```

Auxiliary space used in the above approach is O(n). It can be reduced.

The idea remains the same as discussed in the previous approach. Sort the interval array in the increasing order of the lower limit. Once you have sorted intervals, you can combine all intervals in a linear traversal.

Following is the detailed step by step algorithm:

Let `last`

be the last interval of non-overlapping intervals. `last`

= 0.

Iterating over `intervals`

, starting from second interval (1 <= `i`

<= `n`

- 1)

- Check if
`intervals[i]`

is overlapping with`intervals[last]`

- If overlapping, merge
`intervals[i]`

and`intervals[last]`

, then to merge them, it is sufficient to update only endpoint of`intervals[last]`

as it is guaranteed that the lower limit of`intervals[last]`

<= lower limit of`intervals[i][0]`

as the array is sorted by starting point. - If non-overlapping, we increment last and moving on,
`intervals[i]`

is the new interval under test of overlapping with following intervals.

- If overlapping, merge
- repeat step 1 for
`i`

=`i`

+ 1.

O(n * log(n)) where `n`

is length of `intervals`

.

O(1).

All updates are done in-place. No extra space is used.

O(n) where `n`

is length of `intervals`

.

```
/*
Asymptotic complexity in terms of the length of the given list \`n\`:
* Time: O(n * log(n)).
* Auxiliary space: O(1).
* Total space: O(n).
*/
static ArrayList<ArrayList<Integer>> get_merged_intervals(ArrayList<ArrayList<Integer>> intervals) {
// Sorting the input interval array by their starting points in increasing order
Collections.sort(intervals, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> object1, ArrayList<Integer> object2) {
int x = object1.get(0) - object2.get(0);
if (x != 0) {
return x;
} else {
return object1.get(1) - object2.get(1);
}
}
});
int last = 0;
for (int i = 1; i < intervals.size(); i++) {
// Checking if intervals[last] and intervals[i] overlap.
if (intervals.get(last).get(1) >= intervals.get(i).get(0)) {
// If overlapping, then merge intervals[i] into intervals[last]
// For merging them, it is sufficient to update only endpoint of intervals[last] as
// it is guaranteed that intervals[last][0]<=intervals[i][0] , last<i
intervals.get(last).set(1, Math.max(intervals.get(last).get(1), intervals.get(i).get(1)));
} else {
// intervals[last] and intervals[i] are found non-overlapping.
// Moving on, intervals[i] is the new interval under test of overlapping with following intervals.
last++;
intervals.set(last, intervals.get(i));
}
}
return new ArrayList<>(intervals.subList(0, last + 1));
}
```

We hope that these solutions to merging overlapping intervals have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart