Start practising

Detect overlap sorted intervals

Easy Intervals Basics

Detect overlap sorted intervals is a easy intervals problem solved with the basics pattern. The best approach, using the order, runs in O(1) time and O(1) space. Below are 2 approaches in Java, from general formula up.

Problem

Given two intervals where the first one starts no later than the second, decide whether they overlap. Knowing the order reduces the check to a single comparison.

Examples

Example 1

Input
a = [1, 4], b = [3, 7] (a starts first)
Output
true

Example 2

Input
a = [1, 2], b = [5, 6]
Output
false

Constraints

  • a.start <= b.start (sorted by 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
General formulaO(1)O(1)
Using the orderO(1)O(1)

1General formula

TimeO(1)
SpaceO(1)

Use the unsorted check max(starts) <= min(ends). It works, but ignores what you know about the order.

  1. return max(a0, b0) <= min(a1, b1).
Java
class Solution {
    static boolean overlap(int[] a, int[] b) {
        return Math.max(a[0], b[0]) <= Math.min(a[1], b[1]);
    }
}

2Using the order

TimeO(1)
SpaceO(1)

If a starts first, b overlaps a exactly when b starts before a ends. This single check is what you run on neighbouring intervals after sorting, as in Meeting Rooms and Merge Intervals.

  1. return b.start <= a.end.
Java
class Solution {
    static boolean overlap(int[] a, int[] b) {
        return b[0] <= a[1];
    }
}

Edge cases to test

  • b starts exactly at a's end
  • b is inside a

Hints

Hint 1

When a starts first, only one comparison matters.

FAQ

What is the best time complexity for Detect overlap sorted intervals?

Using the order runs in O(1) time and O(1) extra space.

Which pattern does Detect overlap sorted intervals use?

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

Is there a brute force solution for Detect overlap sorted intervals?

Yes. General formula takes O(1) time and O(1) space. Use the unsorted check max(starts) <= min(ends).

Which edge cases should I test for Detect overlap sorted intervals?

b starts exactly at a's end; b is inside a.