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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 8 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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).
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.
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.