# Merge Overlapping Intervals

Discover the technique to detect zero sum subarrays in a set of numbers with this comprehensive guide.

array
medium

Published At

3/12/2023

Write a function that takes in a non-empty array of arbitrary intervals, merges any overlapping intervals, and returns the new intervals in no particular order.

Each interval is an array of two integers, with interval[0] as the start of the interval and interval[1] as the end of the interval.

Note that back-to-back intervals aren't considered to be overlapping. For example, [1, 5] and [6, 7] aren't overlapping; however, [1, 6] and [6, 7] are indeed overlapping.

Also note that the start of any particular interval will always be less than or equal to the end of that interval.

### Sample Input

js
``intervals = [[1, 2], [3, 5], [4, 7], [6, 8], [9, 10]]``
js
``intervals = [[1, 2], [3, 5], [4, 7], [6, 8], [9, 10]]``

### Sample Output

js
``````[[1, 2], [3, 8], [9, 10]]
// Merge the intervals [3, 5], [4, 7], and [6, 8].
// The intervals could be ordered differently.``````
js
``````[[1, 2], [3, 8], [9, 10]]
// Merge the intervals [3, 5], [4, 7], and [6, 8].
// The intervals could be ordered differently.``````

### Hints

Hint 1

The problem asks you to merge overlapping intervals. How can you determine if two intervals are overlapping?

Hint 2

Sort the intervals with respect to their starting values. This will allow you to merge all overlapping intervals in a single traversal through the sorted intervals

Hint 3

After sorting the intervals with respect to their starting values, traverse them, and at each iteration, compare the start of the next interval to the end of the current interval to look for an overlap. If you find an overlap, mutate the current interval so as to merge the next interval into it.

Optimal Space & Time Complexity

O(nlog(n)) time | O(n) space - where n is the length of the input array

Solution-1
js
``````function mergeOverlappingIntervals(array) {
let arr = []
let arrLen = array.length

array.sort((a, b) => a[0] - b[0])

let i = 0
let j = 1

while (i < arrLen) {
let iStart = array[i][0]
let iEnd = array[i][1]

if (i + 1 == arrLen) {
arr.push([iStart, iEnd])
break;
}

while (j < arrLen && array[j][0] <= iEnd) {
iEnd = Math.max(array[j][1], iEnd)
j++
}
arr.push([iStart, iEnd])
i = j
j++
}

return arr;
}``````
Solution-1
js
``````function mergeOverlappingIntervals(array) {
let arr = []
let arrLen = array.length

array.sort((a, b) => a[0] - b[0])

let i = 0
let j = 1

while (i < arrLen) {
let iStart = array[i][0]
let iEnd = array[i][1]

if (i + 1 == arrLen) {
arr.push([iStart, iEnd])
break;
}

while (j < arrLen && array[j][0] <= iEnd) {
iEnd = Math.max(array[j][1], iEnd)
j++
}
arr.push([iStart, iEnd])
i = j
j++
}

return arr;
}``````
Solution-2
js
``````function mergeOverlappingIntervals(array) {
array.sort((a, b) => a[0] - b[0])

const arr = []
let current = array[0]
arr.push(current)

for (const next of array) {
const [start, end] = current
const [nextStart, nextEnd] = next

if (end >= nextStart) {
current[1] = Math.max(end, nextEnd)
} else {
current = next
arr.push(current)
}
}

return arr;
}``````
Solution-2
js
``````function mergeOverlappingIntervals(array) {
array.sort((a, b) => a[0] - b[0])

const arr = []
let current = array[0]
arr.push(current)

for (const next of array) {
const [start, end] = current
const [nextStart, nextEnd] = next

if (end >= nextStart) {
current[1] = Math.max(end, nextEnd)
} else {
current = next
arr.push(current)
}
}

return arr;
}``````

🥷

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek 🙏

## Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

• In-depth looks at my covert projects and musings to ignite your imagination.
• Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
• A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.