K Closest Points to Origin

K Closest Points to Origin is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Top K Elements (Selection/Frequency) subpattern.

Problem statement

Given an array of points where points[i] = [xi, yi] 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., (x1 - x2)2 + (y1 - y2)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 <= 104

- -104 <= xi, yi <= 104

Topics and companies

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

Reported in interviews at Amazon, Apple, Asana, Bloomberg, ByteDance, DoorDash, Facebook, Google, LinkedIn, Microsoft, Uber.

How to practise K Closest Points to Origin on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log k), where n is the number of points. Each point is pushed/popped from the heap at most once, and heap operations are O(log k). time and O(k), for storing the k closest points in the heap. space.

Open K Closest Points to Origin in the code editor, or read the K Closest Points to Origin editorial for a worked solution with its approach and complexity analysis.

Where K Closest Points to Origin sits in the DSA pattern sheet

Problems related to K Closest Points to Origin

Other problems that use the same Top K Elements (Selection/Frequency) and Heap (Priority Queue) Patterns techniques:

Preparing this workspace.