Find Right Interval - Practice Coding Problems

Find Right Interval - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: intervals = [[1,2]]

› Output: [-1]

💡 Note: There is only one interval, no right interval exists for [1,2], so return -1

Example 2 — Multiple Intervals

$ Input: intervals = [[3,4],[2,3],[1,2]]

› Output: [-1,0,1]

💡 Note: For [3,4]: no interval starts >= 4, return -1. For [2,3]: [3,4] starts at 3 >= 3, return index 0. For [1,2]: [2,3] starts at 2 >= 2, return index 1

Example 3 — Self Reference

$ Input: intervals = [[1,4],[2,3],[3,4]]

› Output: [-1,2,2]

💡 Note: For [1,4]: no start >= 4, return -1. For [2,3]: [3,4] starts at 3 >= 3, return index 2. For [3,4]: itself starts at 3 >= 4 is false, but no other valid interval, return 2 (self)

Constraints

1 ≤ intervals.length ≤ 2 × 10⁴
intervals[i].length == 2
-10⁶ ≤ start_i ≤ end_i ≤ 10⁶
The start point of each interval is unique.

Visualization

Tap to expand

Understanding the Visualization

Input

Array of intervals with unique start times

Process

For each interval, find the interval with smallest start ≥ end

Output

Array of right interval indices or -1 if none exists

Key Takeaway

🎯 Key Insight: Sort intervals by start time to enable efficient binary search for the right interval

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to sort intervals by start time to enable binary search. The brute force approach checks all intervals for each query in O(n²) time. The optimal approach sorts start times with indices, then uses binary search to find the smallest valid start time in O(log n) per query. Overall time: O(n log n), space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Sort + Binary Search	O(n log n)	O(n)	Sort intervals by start time, then use binary search to find right interval
Brute Force	O(n²)	O(1)	For each interval, check all other intervals to find the right one

Sort + Binary Search — Algorithm Steps

Sort intervals by start time
For each interval, binary search for smallest valid start
Return the corresponding original index

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort intervals by start time with original indices

Binary Search

For each interval, binary search for smallest valid start

Result

Return original index of found interval

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int start;
    int index;
} StartIndex;

int compare(const void *a, const void *b) {
    StartIndex *sa = (StartIndex*)a;
    StartIndex *sb = (StartIndex*)b;
    return sa->start - sb->start;
}

int* solution(int** intervals, int intervalsSize, int* returnSize) {
    *returnSize = intervalsSize;
    int* result = (int*)malloc(intervalsSize * sizeof(int));
    
    // Create array of start times with original indices
    StartIndex* starts = (StartIndex*)malloc(intervalsSize * sizeof(StartIndex));
    for (int i = 0; i < intervalsSize; i++) {
        starts[i].start = intervals[i][0];
        starts[i].index = i;
    }
    qsort(starts, intervalsSize, sizeof(StartIndex), compare);
    
    for (int i = 0; i < intervalsSize; i++) {
        int endTime = intervals[i][1];
        // Binary search for first start >= endTime
        int left = 0, right = intervalsSize;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (starts[mid].start >= endTime) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        if (left < intervalsSize) {
            result[i] = starts[left].index;
        } else {
            result[i] = -1;
        }
    }
    
    free(starts);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int** intervals = (int**)malloc(1000 * sizeof(int*));
    int size = 0;
    
    char* token = strtok(line, "[]");
    while (token != NULL) {
        if (strchr(token, ',') != NULL && token[0] != ',' && token[0] != ']') {
            intervals[size] = (int*)malloc(2 * sizeof(int));
            sscanf(token, "%d,%d", &intervals[size][0], &intervals[size][1]);
            size++;
        }
        token = strtok(NULL, "[]");
    }
    
    int returnSize;
    int* result = solution(intervals, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

O(n log n) for sorting + O(n log n) for n binary searches

⚡ Linearithmic

Space Complexity

O(n)

Extra array to store sorted start times with indices

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort + Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler