K Closest Points to Origin Explained: [[1,3],[-2,2],[2,-2]] Walkthrough

Imagine you are building a ride-sharing dispatch system. You have thousands of driver coordinates flooding in every second, and a passenger at the origin $(0,0)$ needs the $k=2$ nearest drivers. You are handed a concrete coordinate set: points = [[1,3],[-2,2],[2,-2]] and you need to find the two closest to the origin. If you blindly calculate and sort every distance from scratch every time a request arrives, your system will choke as the scale of points grows from three to three million.

Calculating raw distances for all points requires floating-point square roots, and sorting the entire dataset just to grab a small slice of size $k$ wastes massive CPU cycles. We need a way to filter or prioritize distances on the fly without paying the penalty of fully sorting every single coordinate in the space. Understanding how to solve this for our small coordinate set unlocks the exact same mechanism used by massive spatial databases.

points = [[1, 3], [-2, 2], [2, -2]]
k = 2
# Goal: Identify why sorting all points might be overkill for large datasets.

When working with spatial coordinate geometry, finding the nearest items to a fixed reference frame like $(0,0)$ requires a reliable measure of separation. For our locked working example of points = $[[1,3],[-2,2],[2,-2]]$ and $k=2$, we do not need the full square root of the Euclidean distance formula to judge proximity. Because the square root function is strictly monotonic for non-negative numbers, comparing the squared distance $x^2+y^2$ preserves the exact same ordering while avoiding costly floating-point square root operations.

Let us map each coordinate pair from our working example to its squared distance metric from the origin:

- Point $[1,3]$ computes to $1^2+3^2=1+9=10$.
- Point $[-2,2]$ computes to $(-2{)}^2+2^2=4+4=8$.
- Point $[2,-2]$ computes to $2^2+(-2{)}^2=4+4=8$.

Our mental model treats the Euclidean plane as a set of concentric circles radiating outward from the origin $(0,0)$. Finding the $k=2$ closest points is equivalent to expanding a circular boundary around the origin until it captures exactly $k$ points. In this geometric landscape, both $[-2,2]$ and $[2,-2]$ sit on a circle of radius $\sqrt{8}$, whereas $[1,3]$ sits further out on a circle of radius $\sqrt{10}$.

Let us apply our squared Euclidean distance model to the locked example where $\text{points}=[[1,3],[-2,2],[2,-2]]$ and $k=2$. Following our geometric blueprint, we bypass square roots to keep our operations strictly within clean integer arithmetic. We calculate the squared distance $x^2+y^2$ for every single coordinate pair in our input list.

1. Compute squared distance for $[1,3]$:

2. Compute squared distance for $[-2,2]$:

3. Compute squared distance for $[2,-2]$:

4. Rank and select $k=2$ items:
Our calculated distances are 10, 8, and 8. Sorting these in ascending order gives us squared distances of 8, 8, and 10. Because we want the $k=2$ smallest entries, we pick the two coordinates tied for a distance of 8.

The coordinate $[1,3]$ with a squared distance of 10 is successfully filtered out.

Try this: Given points = [[1, 3], [-2, 2], [2, -2]] and k = 2, explain what changes in the final selection if k is reduced from 2 to 1.

Now it is your turn to apply the squared distance and selection logic we walked through. In our previous step, we evaluated [[1,3], [-2,2], [2,-2]] for $k=2$ and found that the points [-2,2] and [2,-2] (both with distance squared equal to 8) were closer than [1,3] (distance squared equal to 10).

Consider a slightly modified scenario using the same foundational principles. Suppose your input points are [[1,1], [3,4], [-1,1]] and you need to find the $k=2$ closest points to the origin $(0,0)$. Compute the squared Euclidean distances for each coordinate, rank them, and determine which two points belong in your final result set.

points = [[1, 1], [3, 4], [-1, 1]]
k = 2
# TODO: Compute dist_sq for each point and select the k closest

We started our journey with points = $\{[1,3],[-2,2],[2,-2]\}$ and $k=2$, discovering that squared Euclidean distances $\{10,8,8\}$ let us isolate the two closest coordinates to the origin without computing square roots. But what happens when our coordinate stream grows dynamically, or when our distance metric shifts from physical space to multi-dimensional feature embeddings in a recommendation system?

When scaling this pattern to streaming or high-dimensional applications, the core principle remains identical: maintain a bounded set of size $k$ using a max-heap (or partition buffer) so you never pay the full $mathcalO(NlogN)$ sorting tax for all incoming records. If your coordinates represent customer delivery locations or product vectors, the distance formula might change from $x^2+y^2$ to a dot product or cosine similarity, but the structural flow of filtering, bounding, and selecting top-$k$ elements transfers directly.

Imagine you are building a rideshare matching service where coordinates arrive as a continuous stream, and you must constantly report the $k=2$ closest drivers to a new passenger at the origin $(0,0)$. Instead of sorting all historical driver coordinates every time a new driver logs in, how should you adapt the max-heap logic we used for our sample set to handle incoming updates efficiently?