Start practising

Detect overlap unsorted

Easy Intervals Basics

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

Problem

Given two intervals in no particular order, decide whether they overlap. This is the building block for every interval problem that follows.

Examples

Example 1

Input
a = [5, 9], b = [1, 6]
Output
true
Why
They share [5, 6].

Example 2

Input
a = [7, 8], b = [1, 3]
Output
false

Constraints

  • Each interval is [start, end] with start <= end (closed).
  • You do not know which interval starts first.

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
Case analysisO(1)O(1)
One formulaO(1)O(1)

1Case analysis

TimeO(1)
SpaceO(1)

List the ways two intervals can relate: a entirely before b, b entirely before a, or overlapping. They overlap unless one ends before the other starts.

  1. If a.end < b.start or b.end < a.start, there is no overlap.
  2. Otherwise they overlap.
Java
class Solution {
    static boolean overlap(int[] a, int[] b) {
        if (a[1] < b[0]) return false;   // a entirely before b
        if (b[1] < a[0]) return false;   // b entirely before a
        return true;
    }
}

2One formula

TimeO(1)
SpaceO(1)

The shared part, if any, runs from the later start to the earlier end. It exists when that range is non-empty.

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

Edge cases to test

  • Touching intervals such as [1, 3] and [3, 5] (overlap for closed intervals; decide for half-open)
  • One interval inside the other

Hints

Hint 1

Two intervals overlap exactly when the later start is not after the earlier end: max(starts) <= min(ends).

FAQ

What is the best time complexity for Detect overlap unsorted?

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

Which pattern does Detect overlap unsorted use?

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

Is there a brute force solution for Detect overlap unsorted?

Yes. Case analysis takes O(1) time and O(1) space. List the ways two intervals can relate: a entirely before b, b entirely before a, or overlapping.

Which edge cases should I test for Detect overlap unsorted?

Touching intervals such as [1, 3] and [3, 5] (overlap for closed intervals; decide for half-open); One interval inside the other.