Coding Interview Questions | Merge Intervals

January 25th, 2024

Merge Intervals Problem Introduction:

This summary will talk about my solution to the merge intervals problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

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

How do you solve the Merge Intervals Problem?

Solution:

function merge(intervals: number[][]): number[][] {
  if (intervals.length <= 1) {
    return intervals;
  }

  // Sort intervals based on the start value
  intervals.sort((a, b) => a[0] - b[0]);

  const mergedIntervals: number[][] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const currentInterval = intervals[i];
    const lastMergedInterval = mergedIntervals[mergedIntervals.length - 1];

    // Check for overlap
    if (currentInterval[0] <= lastMergedInterval[1]) {
      // Merge intervals
      lastMergedInterval[1] = Math.max(
        lastMergedInterval[1],
        currentInterval[1]
      );
    } else {
      // No overlap, add the current interval to the result
      mergedIntervals.push(currentInterval);
    }
  }

  return mergedIntervals;
}

Merge Intervals Solution Summary:

Below is a breakdown of the key aspects of the solution above for merging overlapping intervals:

1. Base Case Handling: The algorithm checks if the length of intervals is less than or equal to 1, returning intervals unchanged in this case.

2. Sorting Intervals: The intervals are sorted based on their start values, ensuring a consistent order.

3. Merging Overlapping Intervals: The algorithm iterates through the sorted intervals, comparing each with the last merged interval. If there is an overlap, it merges the intervals by updating the end value of the last merged interval.

4. Updating Result: The merged intervals are stored in the mergedIntervals array. If no overlap is found, the current interval is added to the result.

5. Final Result: The result is an array of non-overlapping intervals obtained from the mergedIntervals array.

Complexities

1. Time Complexity: The time complexity of the solution is dominated by the sorting step, which is O(n log n), where n is the number of intervals. The subsequent iteration through intervals is linear, resulting in an overall time complexity of O(n log n).

2. Space Complexity: The space complexity is primarily influenced by the mergedIntervals array, which has a space complexity of O(n), where n is the number of intervals.