## Problem Given an array of 2D points and an integer `k`, return the `k` points closest to the origin `(0, 0)`. Distance is Euclidean. The result can be in any order. ```python def k_closest(points: list[list[int]], k: int) -> list[list[int]]: pass ``` **Example:** ``` points = [[1,3],[-2,2],[5,8],[0,1]], k = 2 -> [[-2,2],[0,1]] # distances: sqrt(10), sqrt(8), sqrt(89), 1 points = [[3,3],[5,-1],[-2,4]], k = 2 -> [[3,3],[-2,4]] # distances: sqrt(18), sqrt(26), sqrt(20) ``` ## Round 1 - Coding Implement a solution using a max-heap of size `k`. ## Follow-ups 1. What is the time complexity of the heap approach vs. a full sort? When does each become preferable? 2. How would you use the Quickselect algorithm to achieve average O(n) time? 3. If points arrive as a stream and you must always return the current `k` closest, how do you maintain the heap efficiently? 4. How does the solution change if distance is Manhattan distance instead of Euclidean?

InterviewDB Question

Points Search: Find the K Nearest Points to an Origin Using a Priority Queue

phone

Question Details

Problem Given an array of 2D points and an integer k, return the k points closest to the origin (0, 0). Distance is Euclidean. The result can be in any order. Example: Round 1 - Coding Implement a solution using a max-heap of size k. Follow-ups What is the time complexity of the heap approach vs. a full sort? When does each become preferable? How would you use the Quickselect algorithm to achieve average O(n) time? If points arrive as a stream and you must always return the current k closest, ho…

Full Details

🔒

Unlock all Applied Intuition questions

Full insider details, leaked discussions, and candidate experiences.

Get full access — $100 a year, unlimited access

About This Question

This is a reported interview question from a applied intuition interview during the phone round.

It covers the following topics: Heap, Phone, Coding, Queue, Arrays, Onsite .

Topics

Heap Phone Coding Queue Arrays Onsite

Points Search: Find the K Nearest Points to an Origin Using a Priority Queue

Question Details

Full Details

About This Question

Topics

More Applied Intuition Interview Questions