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:

✅ Solution '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⁴

Solution

The Euclidean distance of a point P(x,y) from the origin can be calculated through the following formula:

This problem follows the Top ‘K’ Numbers pattern. The only difference in this problem is that we need to find the closest point (to the origin) as compared to finding the largest numbers.

Following a similar approach, we can use a Max Heap to find ‘K’ points closest to the origin. While iterating through all points, if a point (say ‘P’) is closer to the origin than the top point of the max-heap, we will remove that top point from the heap and add ‘P’ to always keep the closest points in the heap.

Code

Here is what our algorithm will look like:

java

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 + "] ");
  }
}

Time Complexity

The time complexity of this algorithm is as we iterating all points and pushing them into the heap.

Space Complexity

The space complexity will be because we need to store ‘K’ point in the heap.

🤖 Don't fully get this? Learn it with Claude

Stuck on 'K' Closest Points to the Origin? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

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 approach visually

See the technique, not just code.

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.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

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.

🔁 Drill the pattern

Lock in recognition with look-alikes.

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.

📝 My notes

← Remove Nth Node From End of List Distribute Coins in Binary Tree →