Is Find Right Interval easy or hard?

Find Right Interval is classified as a Medium difficulty problem. The challenge lies in recognizing that sorting interval starts enables efficient binary search instead of scanning all intervals.

Find Right Interval Python/Java solution

In Python or Java, the standard implementation stores interval starts with indices, sorts them, and applies binary search for each interval's end value. This results in O(n log n) time and O(n) extra space.

How to solve Find Right Interval in O(n)?

A strict O(n) solution is not possible because intervals must be ordered by start values to locate the next valid interval efficiently. The closest practical approach is sorting followed by a linear scan using two pointers, which runs in O(n log n) due to the sorting step.

What is the best approach for Find Right Interval?

The most common solution sorts interval start points and uses binary search to find the smallest start >= each interval's end. This runs in O(n log n) time and O(n) space. It is straightforward and commonly expected in coding interviews.

Is Find Right Interval asked at Google/Amazon/Meta?

Interval search and binary search problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of interval processing, sorting, and efficient lookups.

What data structure is used in Find Right Interval?

The typical solution uses arrays or lists combined with sorting and binary search. Some implementations store pairs of (start, original index) to preserve the original interval positions after sorting.

What is the time complexity of Find Right Interval?

The optimal time complexity is O(n log n). Sorting the interval starts takes O(n log n), and each interval performs a binary search in O(log n). The overall complexity remains O(n log n) with O(n) additional space.

Description Solution Video 22:39

436. Find Right Interval

Medium56.7% acceptance4 companies

You are given an array of intervals, where intervals[i] = [start_i, end_i] and each start_i is unique.

The right interval for an interval i is an interval j such that start_j >= end_i and start_j is minimized. Note that i may equal j.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Example 1:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start₀ = 3 is the smallest start that is >= end₁ = 3.
The right interval for [1,2] is [2,3] since start₁ = 2 is the smallest start that is >= end₂ = 2.

Example 3:

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start₂ = 3 is the smallest start that is >= end₁ = 3.

Constraints: