DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Merge Intervals

#algorithms #interview #java #leetcode

One of the most common interval-based interview questions is Merge Intervals. At first glance, it looks like a simulation problem, but the real trick is recognizing that sorting allows us to process all overlaps in a single pass.

Let's break it down.

Problem Statement

Given an array of intervals where:

intervals[i] = [starti, endi]
Enter fullscreen mode Exit fullscreen mode

Merge all overlapping intervals and return the resulting non-overlapping intervals.

Example 

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

Output:
[[1,6],[8,10],[15,18]]
Enter fullscreen mode Exit fullscreen mode

Since [1,3] and [2,6] overlap, they can be merged into [1,6].

Brute Force Approach

Interview Explanation

My first observation would be that overlapping intervals need to be grouped together.

A straightforward approach is to sort the intervals and then, for every interval, keep checking future intervals that overlap with it. Whenever an overlap occurs, update the ending point and continue.

Once no overlap exists, store the merged interval and move forward.

Time Complexity 

O(N²)
Enter fullscreen mode Exit fullscreen mode

Space Complexity 

O(N)
Enter fullscreen mode Exit fullscreen mode

Brute Force Code 

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

List<int[]> result = new ArrayList<>();

for (int i = 0; i < intervals.length; i++) {

    int start = intervals[i][0];
    int end = intervals[i][1];

    while (i + 1 < intervals.length &&
           intervals[i + 1][0] <= end) {

        end = Math.max(end, intervals[i + 1][1]);
        i++;
    }

    result.add(new int[]{start, end});
}
Enter fullscreen mode Exit fullscreen mode

Key Observation

After sorting by start time:

[1,3] [2,6] [8,10] [15,18]
Enter fullscreen mode Exit fullscreen mode

All overlapping intervals become adjacent.

This means we don't need to repeatedly compare with many future intervals.

We only need to compare with the most recently merged interval.

That observation reduces the problem to a single linear scan.

Optimal Approach

Algorithm

  1. Sort intervals by start time.
  2. Maintain a list of merged intervals.
  3. If the current interval overlaps with the last merged interval:

  • Extend the end time.

    1. Otherwise:

  • Add a new interval.

Optimal Java Solution 

class Solution {
    public int[][] merge(int[][] intervals) {

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> merged = new ArrayList<>();

        for (int[] interval : intervals) {

            if (merged.isEmpty() ||
                merged.get(merged.size() - 1)[1] < interval[0]) {

                merged.add(interval);

            } else {

                merged.get(merged.size() - 1)[1] =
                    Math.max(
                        merged.get(merged.size() - 1)[1],
                        interval[1]
                    );
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run

Input 

[[1,3],[2,6],[8,10],[15,18]]
Enter fullscreen mode Exit fullscreen mode

After Sorting 

[[1,3],[2,6],[8,10],[15,18]]
Enter fullscreen mode Exit fullscreen mode

Step 1

Add first interval:

[[1,3]]
Enter fullscreen mode Exit fullscreen mode

Step 2

Current interval:

[2,6]
Enter fullscreen mode Exit fullscreen mode

Check overlap:

2 <= 3
Enter fullscreen mode Exit fullscreen mode

Yes, merge.

[[1,6]]
Enter fullscreen mode Exit fullscreen mode

Step 3

Current interval:

[8,10]
Enter fullscreen mode Exit fullscreen mode

Check overlap:

8 <= 6
Enter fullscreen mode Exit fullscreen mode

No.

Add it.

[[1,6],[8,10]]
Enter fullscreen mode Exit fullscreen mode

Step 4

Current interval:

[15,18]
Enter fullscreen mode Exit fullscreen mode

Check overlap:

15 <= 10
Enter fullscreen mode Exit fullscreen mode

No.

Add it.

[[1,6],[8,10],[15,18]]
Enter fullscreen mode Exit fullscreen mode

What Interviewers Want To Hear

A good interview answer is:

Since interval overlap depends on ordering, I would first sort the intervals by start time. After sorting, all overlapping intervals become adjacent, allowing me to merge them in a single pass by comparing only with the most recently merged interval.

This demonstrates both pattern recognition and optimization thinking.

Complexity Analysis

Operation Complexity
Sorting O(N log N)
Traversal O(N)
Total O(N log N)
Extra Space O(N)

Key Takeaway

Whenever you see:

  • Merge intervals
  • Meeting rooms
  • Insert interval
  • Non-overlapping intervals

Think:

Sort first. Then process intervals from left to right.

This pattern appears repeatedly in coding interviews and is worth mastering.

Striver SDE Sheet Challenge 🚀

Follow along for more daily solutions from the Striver SDE Sheet.

GitHub: https://github.com/codewithjaspreet
LinkedIn: https://linkedin.com/in/jaspreetsinghsodhi
Medium: https://medium.com/@jaspreet.dev

Top comments (0)