436. Find Right Interval LeetCode Solution

Last updated: February 17, 2025

In this guide, you will get 436. Find Right Interval LeetCode Solution with the best time and space complexity. The solution to Find Right Interval problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find Right Interval solution in C++
Find Right Interval solution in Java
Find Right Interval solution in Python
Additional Resources

436. Find Right Interval LeetCode Solution image

Problem Statement of Find Right Interval

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.
The right interval for an interval i is an interval j such that startj >= endi and startj 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 start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 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 start2 = 3 is the smallest start that is >= end1 = 3.

Constraints:

1 <= intervals.length <= 2 * 104
intervals[i].length == 2
-106 <= starti <= endi <= 106
The start point of each interval is unique.

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

436. Find Right Interval LeetCode Solution in C++

class Solution {
 public:
  vector<int> findRightInterval(vector<vector<int>>& intervals) {
    vector<int> ans;
    map<int, int> startToIndex;

    for (int i = 0; i < intervals.size(); ++i)
      startToIndex[intervals[i][0]] = i;

    for (const vector<int>& interval : intervals) {
      const auto it = startToIndex.lower_bound(interval[1]);
      ans.push_back(it == startToIndex.cend() ? -1 : it->second);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

436. Find Right Interval LeetCode Solution in Java

class Solution {
  public int[] findRightInterval(int[][] intervals) {
    final int n = intervals.length;

    int[] ans = new int[n];
    TreeMap<Integer, Integer> startToIndex = new TreeMap<>();

    for (int i = 0; i < n; ++i)
      startToIndex.put(intervals[i][0], i);

    for (int i = 0; i < n; ++i) {
      Map.Entry<Integer, Integer> entry = startToIndex.ceilingEntry(intervals[i][1]);
      ans[i] = entry == null ? -1 : entry.getValue();
    }

    return ans;
  }
}
// code provided by PROGIEZ

436. Find Right Interval LeetCode Solution in Python

from sortedcontainers import SortedDict


class Solution:
  def findRightInterval(self, intervals: list[list[int]]) -> list[int]:
    ans = []
    startToIndex = SortedDict()

    for i, (start, end) in enumerate(intervals):
      startToIndex[start] = i

    for start, end in intervals:
      i = startToIndex.bisect_left(end)
      ans.append(-1 if i == len(startToIndex) else startToIndex.peekitem(i)[1])

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents