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)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay