 Register for our webinar

### How to Nail your next Technical Interview

1 hour 1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name  Step 1  Step 2
Congratulations!
You have registered for our webinar Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone  Step 1  Step 2 Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.  ## You may be missing out on a 66.5% salary hike* ### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.  ## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.  # Merge Overlapping Intervals Problem Statement

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.

## Example One

``````{
"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].

## Example Two

``````{
"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.

## Notes

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

Constraints:

• 1 <= number of input intervals <= 105
• -109 <= lower limit of an interval <= upper limit of an interval <= 109

We provided three solutions.

# Merge Overlapping Intervals Solution 1: Brute Force

A naive approach would be iterating over `intervals` and checking if `intervals[i]` is already removed.

1. If it is, continue.
2. 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).

## Time Complexity

O(n2) where `n` is length of `intervals`.

## Auxiliary Space Used

O(1).

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

## Space Complexity

O(n) where `n` is length of `intervals`.

## Code For Merge Overlapping Intervals Solution 1: Brute Force

``````
/*
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))) {
}
}

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));
}

``````

# Merge Overlapping Intervals Solution 2: Other

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.

1. Sort the intervals based on increasing order of starting time.
2. Push the first interval on to a stack.
3. 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.
4. At the end stack contains the merged intervals.

## Time Complexity

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)).

## Auxiliary Space Used

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.)

## Space Complexity

O(n) where `n` is length of `intervals`.

## Code For Merge Overlapping Intervals Solution 2: Other

``````
/*
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);
}

``````

# Merge Overlapping Intervals Solution 3: Optimal

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)

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]` 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.
2. repeat step 1 for `i` = `i` + 1.

## Time Complexity

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)).

## Auxiliary Space Used

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.)

## Space Complexity

O(n) where `n` is length of `intervals`.

## Code For Merge Overlapping Intervals Solution 3: Optimal

``````
/*
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]<=intervals[i] , 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:

### Try yourself in the Editor

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

# Merge Overlapping Intervals Problem Statement

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.

## Example One

``````{
"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].

## Example Two

``````{
"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.

## Notes

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

Constraints:

• 1 <= number of input intervals <= 105
• -109 <= lower limit of an interval <= upper limit of an interval <= 109

We provided three solutions.

# Merge Overlapping Intervals Solution 1: Brute Force

A naive approach would be iterating over `intervals` and checking if `intervals[i]` is already removed.

1. If it is, continue.
2. 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).

## Time Complexity

O(n2) where `n` is length of `intervals`.

## Auxiliary Space Used

O(1).

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

## Space Complexity

O(n) where `n` is length of `intervals`.

## Code For Merge Overlapping Intervals Solution 1: Brute Force

``````
/*
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))) {
}
}

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));
}

``````

# Merge Overlapping Intervals Solution 2: Other

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.

1. Sort the intervals based on increasing order of starting time.
2. Push the first interval on to a stack.
3. 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.
4. At the end stack contains the merged intervals.

## Time Complexity

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)).

## Auxiliary Space Used

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.)

## Space Complexity

O(n) where `n` is length of `intervals`.

## Code For Merge Overlapping Intervals Solution 2: Other

``````
/*
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);
}

``````

# Merge Overlapping Intervals Solution 3: Optimal

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)

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]` 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.
2. repeat step 1 for `i` = `i` + 1.

## Time Complexity

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)).

## Auxiliary Space Used

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.)

## Space Complexity

O(n) where `n` is length of `intervals`.

## Code For Merge Overlapping Intervals Solution 3: Optimal

``````
/*
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]<=intervals[i] , 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:

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve. Hosted By
Ryan Valles
Founder, Interview Kickstart Accelerate your Interview prep with Tier-1 tech instructors 360° courses that have helped 14,000+ tech professionals 100% money-back guarantee*