Use PriorityQueue


  • 0
    G

    Just to provide another solution using PriorityQueue. Much slower.

    class Solution {
        public int maxDistance(List<List<Integer>> arrays) {
            int res = 0, len = arrays.size();
            int[] max = new int[len], min = new int[len];
            for (int i = 0; i < len; i++) {
                List<Integer> tmp = arrays.get(i);
                max[i] = tmp.get(tmp.size() - 1);
                min[i] = tmp.get(0);    
            }
            
            PriorityQueue<Integer> maxpq = new PriorityQueue<>((x, y) -> max[y] - max[x]); // max heap for maximum val
            PriorityQueue<Integer> minpq = new PriorityQueue<>((x, y) -> min[x] - min[y]); // min heap for minimum val
            for (int i = 0; i < len; i++) {
                maxpq.offer(i);
                minpq.offer(i);
            }
            
            int maxres = maxpq.poll(), minres = minpq.poll();
            if (maxres != minres) return max[maxres] - min[minres];
            return Math.max(max[maxres] - min[minpq.poll()], max[maxpq.poll()] - min[minres]);
            //If max and min belong to same group, then max and second min must belong to different group; and 
            // second max and min must also belong to different group.
        }  
    }
    
    

Log in to reply
 

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