Start practising

Merge two sorted intervals

Easy Intervals Basics

Merge two sorted intervals is a easy intervals problem solved with the basics pattern. The best approach, one expression, runs in O(1) time and O(1) space. Below are 2 approaches in Java, from branch on containment up.

Problem

Given two intervals where the first starts no later than the second, merge them if they overlap. It looks trivial, but most bugs in Merge Intervals come from this step.

Examples

Example 1

Input
a = [1, 5], b = [4, 8] (a starts first)
Output
[1, 8]

Example 2

Input
a = [1, 10], b = [2, 3]
Output
[1, 10]
Why
b is inside a, so the end stays 10. This is why you need max(a.end, b.end).

Constraints

  • a.start <= b.start; closed intervals.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Branch on containmentO(1)O(1)
One expressionO(1)O(1)

1Branch on containment

TimeO(1)
SpaceO(1)

If b does not overlap a, no merge. If b is inside a, the result is a. Otherwise it is [a.start, b.end].

  1. b.start > a.end → null.
  2. b.end <= a.end → a.
  3. Else [a.start, b.end].
Java
class Solution {
    static int[] merge(int[] a, int[] b) {
        if (b[0] > a[1]) return null;
        if (b[1] <= a[1]) return a;
        return new int[] { a[0], b[1] };
    }
}

2One expression

TimeO(1)
SpaceO(1)

Given overlap, the merged interval is [a.start, max(a.end, b.end)], which covers both the partial and the contained cases. This is the step inside Merge Intervals.

  1. If b.start > a.end return null; else return [a.start, max(a.end, b.end)].
Java
class Solution {
    static int[] merge(int[] a, int[] b) {
        if (b[0] > a[1]) return null;
        return new int[] { a[0], Math.max(a[1], b[1]) };
    }
}

Edge cases to test

  • b fully inside a (a common bug: using b.end as the new end)

Hints

Hint 1

The start is always a.start. The end is max(a.end, b.end), not b.end.

FAQ

What is the best time complexity for Merge two sorted intervals?

One expression runs in O(1) time and O(1) extra space.

Which pattern does Merge two sorted intervals use?

It is a intervals problem that uses the basics pattern. Other problems with the same pattern: Detect overlap unsorted, Detect overlap sorted intervals, Interval List Intersections.

Is there a brute force solution for Merge two sorted intervals?

Yes. Branch on containment takes O(1) time and O(1) space. If b does not overlap a, no merge.

Which edge cases should I test for Merge two sorted intervals?

b fully inside a (a common bug: using b.end as the new end).