Find Right Interval LeetCode solution in Java

1
/*
2
- Time: O(N*log(N))
3
Loop through the array with n elements and run binary search with log(N) time for each of them.
4

5
- Space: O(N)
6
Used a hashmap map of size N to store the original indeces of intervals
7
 */
8
class Solution {
9
  public int[] findRightInterval(int[][] intervals) {
10
    int n = intervals.length;
11
    int[] res = new int[n];
12
    Map<int[], Integer> map = new HashMap<>();
13
    for (int i = 0; i < n; i++) {
14
      map.put(intervals[i], i);
15
    }
16

17
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
18
    for (int i = 0; i < n; i++) {
19
      int[] interval = binarySearch(intervals, intervals[i][1], i);
20
      res[map.get(intervals[i])] = interval == null ? -1 : map.get(interval);
21
    }
22

23
    return res;
24
  }
25

26
  private int[] binarySearch(int[][] intervals, int target, int start) {
27
    int l = start, r = intervals.length - 1;
28

29
    while (l <= r) {
30
      int m = l + (r - l) / 2;
31
      if (intervals[m][0] >= target) {
32
        // keep moving the right boundary to the left to get the first
33
        // element bigger than target
34
        r = m - 1;
35
      } else {
36
        // if the element we get is bigger than the target, we move the
37
        // left boundary to look at right part of the array
38
        l = m + 1;
39
      }
40
    }
41
    return l == intervals.length ? null : intervals[l];
42
  }
43
}