436. Find Right Interval

436. Find Right Interval (#1 Binary Search + HashTable).java

// Binary Sort + HashTable solution: do binary search for each interval with the help of helper map and array (sort)
// Time: O(nlogn), 15ms
// Space: O(n), 46.5mb
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int len = intervals.length;
        int[] array = new int[len];
        Map<Integer, Integer> map = new HashMap<> ();
        int[] ans = new int[len];
        
        // Exact the begin time and index of all the intervals
        for(int i = 0; i < intervals.length; i++) {
            array[i] = intervals[i][0];
            map.put(intervals[i][0], i);
        }
        Arrays.sort(array);
        
        // Do binary search in the sorted array of begin time for each interval
        for(int i = 0; i < intervals.length; i++) {
            int target = intervals[i][1];
            int begin = 0, end = len - 1, mid, ret = -1;
            
            while(begin <= end) {
                mid = begin + (end - begin) / 2;
                if(array[mid] == target) {
                    ret = mid;
                    break;
                } else if(array[mid] > target) {
                    ret = mid; // Save the last index of the interval whose begin time is larger than target
                    end = mid - 1;
                } else { // array[mid] < target
                    begin = mid + 1;
                }
            }
            if(ret != -1) {
                ans[i] = map.get(array[ret]);
            } else {
                ans[i] = -1;
            }
        }
        
        return ans;
    }
}

436. Find Right Interval (#2 Bucket Sort).java

// Bucket sort solution: Sort the intervals according to start time
// Time: O(n) in average case, O(n^2) in worse case, 2ms
// Space: O(n), 40mb
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        // Find the min and max of start time
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for(int[] interval : intervals) {
            min = Math.min(min, interval[0]);
            max = Math.max(max, interval[0]);
        }
        
        // Build an array of buckets that save the intervals with ceratin beign time
        int[] buckets = new int[max - min + 1];
        for(int i = 0; i < buckets.length; i++) buckets[i] = -1;
        for(int i = 0; i < intervals.length; i++) {
            // Save the index of interval in the buckets
            // Take advantage of that there won't be two intervals with the same begin time
            buckets[intervals[i][0] - min] = i;
        }
        
        // For each interval find the min right interval by traversing the buckets
        int[] ans = new int[intervals.length];
        for(int i = 0; i < intervals.length; i++) {
            ans[i] = -1;
            for(int j = intervals[i][1] - min; j < buckets.length; j++) {
                if(buckets[j] != -1) {
                    ans[i] = buckets[j];
                    break;
                }
            }
        }
        
        return ans;
    }
}

436. Find Right Interval (#3 Hash table).java

// Hash table solution: use NavigableMap find the ceilingEntry every time
// Time: O(n) * O(logn) = O(nlogn) where O(logn) is the time complexity of NavigableMap.ceilingEntry(), 21ms
// Space: O(n), 47.4mb
import java.util.NavigableMap;

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        
        // Make a map of <begin time, index of interval>
        NavigableMap<Integer, Integer> map = new TreeMap<>();
        for(int i = 0; i < intervals.length; i++) {
            map.put(intervals[i][0], i);
        }
        
        // Find the ceilingEntry for each interval
        int[] ans = new int[intervals.length];
        for(int i = 0; i < intervals.length; i++) {
            Map.Entry<Integer, Integer> entry = map.ceilingEntry(intervals[i][1]);
            ans[i] = entry == null ? -1 : entry.getValue();
        }
        
        return ans;
    }
}