DEV Community

Cover image for LeetCode Meditations: Merge Intervals
Eda
Eda

Posted on • Originally published at rivea0.github.io

LeetCode Meditations: Merge Intervals

Let's start with the description for Merge Intervals:

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

For example:

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: Since intervals [1, 3] and [2, 6] overlap, merge them into [1, 6].
Enter fullscreen mode Exit fullscreen mode

Or:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]

Explanation: Intervals [1, 4] and [4, 5] are considered overlapping. 
Enter fullscreen mode Exit fullscreen mode

We can start by sorting the intervals first, so that we can compare them easily later:

intervals.sort((a, b) => a[0] - b[0]);
Enter fullscreen mode Exit fullscreen mode

Also, we can initialize a result array which initially holds the first element of the newly sorted intervals:

let result = [intervals[0]];
Enter fullscreen mode Exit fullscreen mode

We need to track the last merged interval's end to compare it with the start of the current interval we are looking at to check if they overlap.

Note
For two intervals not to overlap, the start of one should be strictly larger than the end of the other or the end of the one should be strictly smaller than the start of the other, as mentioned in our chapter introduction.

If they don't overlap, we can just add that interval to result. Otherwise, we need to update the "last end," effectively merging the intervals:

for (const interval of intervals) {
  const [currentStart, currentEnd] = [interval[0], interval[1]];

  // non-overlapping
  if (result[result.length - 1][1] < currentStart) {
    result.push(interval);
  // overlapping, update last end
  } else {
    result[result.length - 1][1] = Math.max(result[result.length - 1][1], currentEnd);
  }
}
Enter fullscreen mode Exit fullscreen mode

And, the only thing left to do is to return the result:

function merge(intervals: number[][]): number[][] {
  /* ... */
  return result;
}
Enter fullscreen mode Exit fullscreen mode

And, this is how our final solution looks like in TypeScript:

function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);
  let result = [intervals[0]];

  for (const interval of intervals) {
    const [currentStart, currentEnd] = [interval[0], interval[1]];

    // non-overlapping
    if (result[result.length - 1][1] < currentStart) {
      result.push(interval);
    // overlapping, update last end
    } else {
      result[result.length - 1][1] = Math.max(result[result.length - 1][1], currentEnd);
    }
  }

  return result;
}
Enter fullscreen mode Exit fullscreen mode

Time and space complexity

We are sorting intervals, and the built-in sort function has O(n log n)O(n \ log \ n) time complexity. (The looping is O(n)O(n) , but the overall time complexity is O(n log n)O(n \ log \ n) ).

The result array can increase in size as the size of the input array intervals increases, therefore we have O(n)O(n) space complexity.


Next up, we'll take a look at the last problem in the chapter, Non-overlapping Intervals. Until then, happy coding.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

This post blew up on DEV in 2020:

js visualized

🚀⚙️ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! 🥳

Happy coding!

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay