Very easy to understand . No TreeMap. Make use of the return value of Arrays.binarySearch(). 92.34%


  • 0
    A

    The idea is :

    1. Use a HashMap(since, average case O(1) lookup) to store the actual location of the given interval.
    2. Additionally, use an array(to perform the right position using bin search in O(logN) time) to store only the start positions.You will need to find the position where your current interval (i's) end position is best suited.
    3. Iterate over the actual interval array to find the min right position using binsearch and find its actual position using Map
    public class Solution {
        public int[] findRightInterval(Interval[] intervals) {
            int[] arr=new int[intervals.length];
            int[] result=new int[intervals.length];
            Map<Integer,Integer> map = new HashMap<>();
            for (int i=0;i<intervals.length;i++)
            {
                int _start = intervals[i].start;
                
                map.put(_start,i);
                arr[i]=_start;
            }
            Arrays.sort(arr);
            int count =0;
            for (int i=0;i<intervals.length;i++)
            {
               int _end = intervals[i].end;
               int index = Arrays.binarySearch(arr,_end);
               {
                   if(index>=0)
                    result[count++]=map.get(_end);
                   else if (~index<arr.length) //~index gives you the index where the number should ideally be seen in the array.
                    result[count++]=map.get(arr[~index]);// For handling cases like [4,5][2,3],[1,2]
                   else
                    result[count++]=-1;
               }
            }
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.