Java Priority Queue or without Priority Queue


  • 1
    1. With Priority Queue. Scan [k+1, 2K] pair. Heap size is [2, k]. O(klogk) time, O(k) space
    2. Without Priority Queue. O(N^2) time, O(1) space
        final int[][] neighbors = {{0, 1}, {1, 0}};
    
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
          List<int[]> sPairs = new ArrayList<>();
          if (nums1 == null || nums1.length == 0 || nums2 == null
                  || nums2.length == 0 || k == 0) return sPairs;
    
          int len1 = nums1.length, len2 = nums2.length;
          boolean[][] visited = new boolean[len1][len2];
          visited[0][0] = true;
          PriorityQueue<int[]> pq = new PriorityQueue<>((int[] pair1, int[] pair2)->
                  (nums1[pair1[0]] + nums2[pair1[1]]) - (nums1[pair2[0]] + nums2[pair2[1]]));
          pq.offer(new int[]{0, 0});
    
          while (sPairs.size() < k && !pq.isEmpty()) {
            int[] currPair = pq.poll();
            sPairs.add(new int[] {nums1[currPair[0]], nums2[currPair[1]]});
    
            for (int[] neighbor : neighbors) {
              int nums1pos = currPair[0] + neighbor[0];
              int nums2pos = currPair[1] + neighbor[1];
              if (nums1pos < 0 || nums1pos == len1 || nums2pos < 0 || nums2pos == len2 || visited[nums1pos][nums2pos]) {
                continue;
              }
              visited[nums1pos][nums2pos] = true;
              pq.offer(new int[]{nums1pos, nums2pos});
            }
          }
    
          return sPairs;
        }
    
        public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
          List<int[]> sPairs = new ArrayList<>();
          if (nums1 == null || nums1.length == 0 || nums2 == null
                  || nums2.length == 0 || k == 0) return sPairs;
    
          int len1 = nums1.length, len2 = nums2.length;
          int[] nums2idx = new int[len1]; // map to last used element in nums2
          while (sPairs.size() < k) {
            int minSoFar = Integer.MAX_VALUE;
            int nums1pos = -1;
            // find smallest pair
            for (int i = 0; i < len1; i++) {
              if (nums2idx[i] >= len2) {
                continue;
              }
              if (nums1[i] + nums2[nums2idx[i]] <= minSoFar) {
                minSoFar = nums1[i] + nums2[nums2idx[i]];
                nums1pos = i;
              }
            }
    
            if (nums1pos == -1) {
              break;
            }
    
            sPairs.add(new int[]{nums1[nums1pos], nums2[nums2idx[nums1pos]]});
            nums2idx[nums1pos]++;
          }
    
          return sPairs;
        }
    

  • 0

    @coolguy said in Java Priority Queue or without Priority Queue:

    Priority Queue

    PriorityQueue is a Heap, you can use heapsort to sort the k max/min elements without creating new O(k) space.


  • 0

    @nasacj Correct! Updating original post.


Log in to reply
 

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