Here is solutions for K Closest Points to Origin.

1. Understand the problem

• We are given a list of 2D points where each point is [x, y].

• We need to return any K points that are closest to the origin (0, 0).

• Distance is based on Euclidean distance:

distance=sqrt(x^2+y^2)

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. Can K be greater than the number of points?

• Usually guaranteed 1 ≤ K ≤ N, but confirm.

1. Do we need to return the points in sorted order?

• No, any order is acceptable.

1. Are coordinates integers? Can they be negative?

• Yes, integers and can be negative.

1. Can there be duplicate points?

• Yes, duplicates are allowed.

1. What are the constraints on N?

• Important for deciding between O(N log N) vs O(N) solutions.

3. Explore examples.

1. Example 1

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

• Distances:

  • (1,3) → 10

  • (-2,2) → 8 ✅

1. Example 2

Input: points = [[3,3],[5,-1],[-2,4]], K = 2

• Distances:

  • (3,3) → 18

  • (5,-1) → 26

  • (-2,4) → 20

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1 — Sort All Points (Naive) - Time O(NlogN), Space O(1)

• For each point, compute x^2 + y^2

• Sort by distance: O(NlogN)

=> Return top K points.

• Time: O(NlogN).

• Space: O(1).

4.2. Solution 2 — Max Heap of Size K (Optimal for Large N) - Time O(NlogK), Space O(K)

• For each point:

  • Compute distance

  • Push into max heap

  • If heap size > K → pop largest distance

• Time: O(NlogK).

• Space: O(K).

4.3. Solution 3 — Quickselect (Best Average Case) - Time O(N) in average case, Worst Case O(N^2), Space O(N)

Idea:

• Use partition like QuickSort to put the K closest points in the first K positions without full sorting.

• Time Complexity:

  • Average: O(N)

  • Worst: O(N^2) (rare with good pivot)

• Space: O(N)

5. Implement solutions.

5.1. Sorting - Time O(NlogN), Space O(1)

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        points.sort(key=lambda p: p[0]**2 + p[1]**2)
        return points[:k]

• Time: O(NlogN)

• Space: O(1)

5.2. Min Heap - Time O(N + K * logN), Space O(N)

• Idea: Add N items to heap, get only K items from heap => Time O(N + KlogN).

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        minHeap = []
        for x, y in points:
            dist = (x ** 2) + (y ** 2)
            minHeap.append([dist, x, y])

        heapq.heapify(minHeap)
        res = []
        while k > 0:
            dist, x, y = heapq.heappop(minHeap)
            res.append([x, y])
            k -= 1

        return res

• Time: O(N + KlogN)

• Space: O(N)

5.3. Max-Heap - Time O(NlogK), Space O(K)

• Idea: nào lớn hơn thì pop, giữ K cái nhỏ nhất

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        maxHeap = []
        for x, y in points:
            dist = -(x ** 2 + y ** 2)
            heapq.heappush(maxHeap, [dist, x, y])
            if len(maxHeap) > k:
                heapq.heappop(maxHeap)

        res = []
        while maxHeap:
            dist, x, y = heapq.heappop(maxHeap)
            res.append([x, y])
        return res

• Time: O(NlogK)

• Space: O(K)

5.4. Quick Select - Only Need K items smaller than K - Best case O(N), Worst case can O(N^2)

class Solution:
    def kClosest(self, points, k):
        euclidean = lambda x: x[0] ** 2 + x[1] ** 2
        def partition(l, r):
            pivotIdx = r
            pivotDist = euclidean(points[pivotIdx])
            i = l
            for j in range(l, r):
                if euclidean(points[j]) <= pivotDist:
                    points[i], points[j] = points[j], points[i]
                    i += 1
            points[i], points[r] = points[r], points[i]
            return i

        L, R = 0, len(points) - 1
        pivot = len(points)

        while pivot != k:
            pivot = partition(L, R)
            if pivot < k:
                L = pivot + 1
            else:
                R = pivot - 1
        return points[:k]

• Time: O(N) for best case, O(N^2) for worst case.

• Space: O(1) in place

6. Dry run testcases.

points = [[3,3],[5,-1],[-2,4]]
K = 2

• Add to the heap

[(-26, 5, -1), (-18, 3, 3), (-20, -2, 4)]

Size = 3 → pop max (most negative = -26)

=> Final Answer: [[-2, 4], [3, 3]]