``` // 10:37AM - 11:22PM // brutal: FIrst get all distance. Quadratic(distance, i, j). Sort the distance and (i,j) to find the smallest k pais. // O(N^2) + O(N^2*logN^2) +O(K) --> O(N^2*logN^2). Space: O(N^2). // Optimization: define a max heap that keeps smallest K element. Top is the max, if quadratic distance > top heap. Do not insert. // if quad is < top heap, delete the top element in the heap and insert. // O(N^2 * logK). Space O(K). //([1, 2, 4, 7, 11, 16], 2) class Solution { public java.util.List> k_closest_pairs( java.util.List nums, int k) { PriorityQueue pq = new PriorityQueue( (a, b) -> b.compareTo(a)); for (int i = 0; i < nums.size(); i++) { for (int j = i+1; j < nums.size(); j++) { long distance = nums.get(j).longValue() - nums.get(i).longValue(); Element element = new Element(distance, i, j); //(1,1,2), (2,2,4), (3,4,7),(4,7,11),(5,11,16) if (pq.size() < k) { pq.offer(element);//(1,1,2), (2,2,4) } else { Element maxElement = pq.peek(); if (maxElement.compareTo(element) > 0) { pq.poll(); pq.offer(element); } } } } Deque> dq = new ArrayDeque<>(); while(pq.size() != 0) { Element e = pq.poll(); List pair = new ArrayList<>(); pair.add(nums.get(e.i).longValue()); pair.add(nums.get(e.j).longValue()); dq.offerFirst(pair); } List> res = new ArrayList>(dq); return res; } private class Element implements Comparable{ public long distance; public int i; public int j; public Element(long distance, int i, int j) { this.distance = distance; this.i = i; this.j = j; } @Override public int compareTo(Element other) { if (this.distance != other.distance) { return Long.compare(this.distance, other.distance); } if (this.i != other.i) { return Integer.compare(this.i, other.i); } if (this.j != other.j) { return Integer.compare(this.j, other.j); } return 0; } } } ```

Quick Overview

Find the K Closest Pairs in a Sorted Array