973. K Closest Points to Origin

// LeetCode URL: https://leetcode.com/problems/k-closest-points-to-origin/
import java.util.Arrays;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * Using Priority Queue
 *
 * Priority Queue will maintain k closest points.
 *
 * Time Complexity: O(N log K)
 *
 * Space Complexity: O(K)
 *
 * N = Lenght of the input array. K = input K.
 */
class Solution1 {
    public int[][] kClosest(int[][] points, int K) {
        if (points == null || points.length == 0 || K <= 0) {
            return new int[0][0];
        }
        if (K >= points.length) {
            return points;
        }

        PriorityQueue<int[]> queue = new PriorityQueue<>(K + 1, (a, b) -> (distance(b) - distance(a)));

        for (int[] p : points) {
            queue.offer(p);

            if (queue.size() > K) {
                queue.poll();
            }
        }

        int[][] result = new int[K][2];

        Iterator<int[]> itr = queue.iterator();
        int i = 0;
        while (itr.hasNext()) {
            result[i++] = itr.next();
        }

        return result;
    }

    private int distance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

/**
 * Using Kth smalled element algorithm (Quick Select)
 *
 * Time Complexity: Best Case -> O(N). Worst Case -> O(N^2).
 *
 * Space Complexity: O(1)
 *
 * N = Lenght of the input array.
 */
class Solution2 {
    public int[][] kClosest(int[][] points, int K) {
        if (points == null || points.length == 0 || K <= 0) {
            return new int[0][0];
        }

        int len = points.length;
        if (K >= len) {
            return points;
        }

        int left = 0;
        int right = len - 1;

        while (left < right) {
            int pivot = partition(points, left, right);
            if (K == pivot) {
                return Arrays.copyOfRange(points, 0, K);
            }

            if (K < pivot) {
                right = pivot - 1;
            } else {
                left = pivot + 1;
            }
        }
        return Arrays.copyOfRange(points, 0, left);
    }

    private int partition(int[][] points, int l, int r) {
        int pivot = l;
        int k = pivot;
        l++;

        while (l <= r) {
            if (distance(points[l]) <= distance(points[pivot])) {
                k++;
                if (k != l) {
                    swap(points, k, l);
                }
            }
            l++;
        }

        swap(points, k, pivot);
        return k;
    }

    private int distance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }

    private void swap(int[][] points, int i, int j) {
        int[] temp = points[i];
        points[i] = points[j];
        points[j] = temp;
    }
}

/**
 * Using Kth smalled element algorithm (Quick Select with Suffle)
 *
 * This algorithm shuffles the input array. It uses Fisher–Yates shuffle
 * algorithm (https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle)
 *
 * Time Complexity: Best Case -> O(N). Worst Case -> O(N^2).
 *
 * Space Complexity: O(1)
 *
 * N = Lenght of the input array.
 */
class Solution3 {
    public int[][] kClosest(int[][] points, int K) {
        if (points == null || points.length == 0 || K <= 0) {
            return new int[0][0];
        }

        int len = points.length;
        if (K >= len) {
            return points;
        }

        shuffle(points);

        int left = 0;
        int right = len - 1;

        while (left < right) {
            int pivot = partition(points, left, right);
            if (K == pivot) {
                return Arrays.copyOfRange(points, 0, K);
            }

            if (K < pivot) {
                right = pivot - 1;
            } else {
                left = pivot + 1;
            }
        }
        return Arrays.copyOfRange(points, 0, left);
    }

    private int partition(int[][] points, int l, int r) {
        int pivot = l;
        int k = pivot;
        l++;

        while (l <= r) {
            if (distance(points[l]) <= distance(points[pivot])) {
                k++;
                if (k != l) {
                    swap(points, k, l);
                }
            }
            l++;
        }

        swap(points, k, pivot);
        return k;
    }

    private int distance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }

    private void swap(int[][] points, int i, int j) {
        int[] temp = points[i];
        points[i] = points[j];
        points[j] = temp;
    }

    private void shuffle(int[][] points) {
        Random rand = new Random();
        for (int i = 1; i < points.length; i++) {
            int idx = rand.nextInt(i + 1);
            if (idx != i) {
                swap(points, idx, i);
            }
        }
    }
}