Crack the Backend

Problem Statement

Given an array points where points[i] = [x_i, y_i] and an integer k, return the k closest points to the origin (0, 0). Distance is Euclidean: sqrt(x^2 + y^2) (you may compare x^2 + y^2 to avoid floating point). The answer can be in any order.

Key Observations

Max-heap of size k: Keep the k closest points. Use a max-heap by distance (so the root is the farthest among the k). For each point: if size < k, add it; else if its distance < heap's max (root), replace the root. Result = all heap elements. O(n log k).
Quickselect by distance for O(n) average.

Approach

High-level: Max-heap by distance (e.g. compare -(xx+yy)). For each point: if size < k offer; else if dist < peek's dist then poll and offer. Return heap to array.

Steps: PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->(b[0]*b[0]+b[1]*b[1])-(a[0]*a[0]+a[1]*a[1])); for (int[] p : points) { if (pq.size()<k) pq.offer(p); else if (dist(p)<dist(pq.peek())) { pq.poll(); pq.offer(p); } } return pq to array.

Implementation

Java

public int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> b[0]*b[0]+b[1]*b[1] - a[0]*a[0]-a[1]*a[1]);

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

        if (pq.size() > k) {
            pq.poll();
        }
    }

    return pq.toArray(int[][]::new);
}

Test Cases

Example 1

Input

points = [[1,3],[-2,2]], k = 1

Expected

[[-2,2]]

Explanation

Closest is (-2,2).

Complexity Analysis

Time: typically O(n log k) or O(n log n).
Space: O(k) or O(n).

Follow-ups

Stream: process one element at a time.