Find Right Interval

MediumBinary Searchbinary search

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an array intervals where intervals[i] = [start_i, end_i] and every start_i is **distinct**. For each interval i, its **right interval** is the interval j whose start satisfies start_j >= end_i and, among all such intervals, has the smallest start_j. Note j may equal i (when start_i == end_i). Return an array ans where ans[i] is the index j of the right interval of interval i, or -1 if none exists. Aim for O(n log n) time.

Examples

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Nothing starts at or after 4. For [2,3] the smallest start >= 3 is interval 0. For [1,2] it is interval 1.
Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Only [2,3] has an interval starting at or after its end (interval 2 starts at 3).
Input: intervals = [[5,5]]
Output: [0]
The interval's own start 5 is >= its end 5, so it is its own right interval.

Constraints

  • 1 <= intervals.length <= 2 * 10^4
  • intervals[i].length == 2
  • -10^6 <= start_i <= end_i <= 10^6
  • All start_i are distinct

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search problems