K Closest Points to Origin

LeetCode 1014 | Difficulty: Medium

Medium

Problem Description

Given an array of points where points[i] = [x~i~, y~i~] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x~1~ - x~2~)^2 + (y~1~ - y~2~)^2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Constraints:

- `1 <= k <= points.length <= 10^4`

- `-10^4 <= x~i~, y~i~ <= 10^4`

Topics: Array, Math, Divide and Conquer, Geometry, Sorting, Heap (Priority Queue), Quickselect

---

Approach

Mathematical

Look for mathematical patterns or formulas. Consider: modular arithmetic, GCD/LCM, prime factorization, combinatorics, or geometric properties.

When to use

Problems with clear mathematical structure, counting, number properties.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 460 ms)

Metric	Value
Runtime	460 ms
Memory	47.7 MB
Date	2019-12-04

Solution

public class Solution {
    public int[][] KClosest(int[][] points, int K) {
        int len = points.Length, l = 0, r = len - 1;
    while (l <= r)
    {
        int mid = helper(points, l, r);
        if (mid == K) break;
        if (mid < K)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return points.Take(K).ToArray();
    }
    
    private int helper(int[][] points, int lo, int hi)
{
    int[] pivot = points[hi];

    var i = lo;

    for (int j = lo; j < hi; j++)
    {
        if (compare(points[j], pivot) <= 0)
        {
            swap(points, i, j);
            i++;
        }
    }
    swap(points, i, hi);
    return i;

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

private int compare(int[] p1, int[] p2)
{
    return p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1];
}
    
    
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.