medium 'K' Closest Points to the Origin

Problem Statement

Given an array of points in a 2D plane, find ‘K’ closest points to the origin.

Example 1:

Input: points = [[1,2],[1,3]], K = 1
Output: [[1,2]]
Explanation: The Euclidean distance between (1, 2) and the origin is sqrt(5).
The Euclidean distance between (1, 3) and the origin is sqrt(10).
Since sqrt(5) < sqrt(10), therefore (1, 2) is closer to the origin.

Example 2:

Input: point = [[1, 3], [3, 4], [2, -1]], K = 2
Output: [[1, 3], [2, -1]]

Constraints:

• 1 <= k <= points.length <= 10⁴
• -10⁴ <= x_i, y_i <= 10⁴

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — 'K' Closest Points to the Origin medium

0. Pattern family

Family: Heap / quickselect on squared distance

1. Why / judgment (K3)

K nearest by Euclidean distance from origin. Compare on x²+y² (no sqrt). Max-heap of size k or quickselect for average linear.

1a. Reference solution — size-k max-heap

Keep a max-heap keyed by squared distance and cap it at size k. For every point: push it, then if the heap grew to k+1 evict the top (the current farthest). Whatever survives is the k closest. Why a max-heap and not a min-heap? The root is the worst of the k points we are keeping, so a new candidate only has to beat that one element to earn a place — an O(log k) decision instead of scanning all k.

public int[][] kClosest(int[][] points, int k) {
    // Max-heap of size k, ordered by squared distance (farthest on top).
    PriorityQueue<int[]> heap = new PriorityQueue<>(
        (a, b) -> (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1]));
    for (int[] p : points) {
        heap.offer(p);              // push current point            O(log k)
        if (heap.size() > k)        // heap too big? drop the farthest
            heap.poll();            //                                O(log k)
    }
    int[][] ans = new int[k][2];    // survivors = k closest
    for (int i = 0; i < k; i++) ans[i] = heap.poll();
    return ans;
}

Heap-contents trace on points=[[1,1],[2,2],[0,1]], k=2 (squared distances: [1,1]→2, [2,2]→8, [0,1]→1):

insert [1,1] (d=2): push          → heap {[1,1]:2}                 size 1 ≤ k
insert [2,2] (d=8): push          → heap {[1,1]:2, [2,2]:8}        size 2 ≤ k
insert [0,1] (d=1): push          → heap {[1,1]:2, [2,2]:8, [0,1]:1}  size 3 > k
                    pop max (d=8)  → heap {[0,1]:1, [1,1]:2}        evict [2,2]
result = the two closest: [0,1] (d=1) and [1,1] (d=2); [2,2] (d=8) correctly dropped ✓

Complexity derivation: each of the n points does one push and at most one pop, each O(log k) because the heap never exceeds size k+1 → total O(n log k) time. The heap holds at most k elements → O(k) extra space. (Full sort would be O(n log n); quickselect is O(n) average but O(n²) worst and clobbers input order.)

2. Worked complexity / derivation (K11)

Max-heap of k: O(n log k). Full sort O(n log n). Quickselect average O(n), worst O(n²). Space O(k) or O(1) in-place select.

3. Pattern + recognition + when-NOT (K12)

Name: TOP-K BY KEY (heap or quickselect)

Recognition: return k closest / smallest under a numeric key; n large, k≪n → heap.

When-NOT: Need all sorted → sort. Dynamic inserts of points → online structure. Exact order among ties may need secondary key.

4. Edge hand-run (K13)

points=[[1,3],[-2,2]] k=1 → [-2,2] (4<10). k=n → all. k=1 single point. origin [0,0] distance 0 included if present.

5. Interviewer follow-ups & drills

Q1. Why skip sqrt?
Model answer: Monotone for non-neg distances; avoids float noise.

Q2. Max vs min heap?
Model answer: Max-heap of size k keeps the k smallest; root is current worst of the k.

Q3. Quickselect risk?
Model answer: Worst-case quadratic without careful pivot; heap is predictable O(n log k).

Input: points = [[1,2],[1,3]], K = 1
Output: [[1,2]]
Explanation: The Euclidean distance between (1, 2) and the origin is sqrt(5).
The Euclidean distance between (1, 3) and the origin is sqrt(10).
Since sqrt(5) < sqrt(10), therefore (1, 2) is closer to the origin.

Input: point = [[1, 3], [3, 4], [2, -1]], K = 2
Output: [[1, 3], [2, -1]]

import java.util.*;

// class Point {
//   int x;
//   int y;

//   public Point(int x, int y) {
//     this.x = x;
//     this.y = y;
//   }

//   public int distFromOrigin() {
//     // ignoring sqrt
//     return (x * x) + (y * y);
//   }
// }

class Solution {

  public List<Point> findClosestPoints(Point[] points, int k) {
    PriorityQueue<Point> maxHeap = new PriorityQueue<>(
      (p1, p2) -> p2.distFromOrigin() - p1.distFromOrigin()
    );
    // put first 'k' points in the max heap
    for (int i = 0; i < k; i++) maxHeap.add(points[i]);

    // go through the remaining points of the input array, if a point is closer to the
    // origin than the top point of the max-heap, remove the top point from heap and add
    // the point from the input array
    for (int i = k; i < points.length; i++) {
      if (points[i].distFromOrigin() < maxHeap.peek().distFromOrigin()) {
        maxHeap.poll();
        maxHeap.add(points[i]);
      }
    }

    // the heap has 'k' points closest to the origin, return them in a list
    return new ArrayList<>(maxHeap);
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    Point[] points = new Point[] {
      new Point(1, 3),
      new Point(3, 4),
      new Point(2, -1),
    };
    List<Point> result = sol.findClosestPoints(points, 2);
    System.out.print("Here are the k points closest the origin: ");
    for (Point p : result) System.out.print("[" + p.x + " , " + p.y + "] ");
  }
}

Heap: each of n inserts/pops O(log k) → O(n log k), space O(k). Sort all O(n log n). Quickselect avg O(n).

[[0,1],[1,0]] k=2 → both. [[1,3],[-2,2]] k=1 → [-2,2]. Duplicate distances both valid any order.

I'm working on the problem **'K' Closest Points to the Origin** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **'K' Closest Points to the Origin** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **'K' Closest Points to the Origin**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **'K' Closest Points to the Origin**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.