Skip to content

Nearest Delivery Drops

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 11 Session 2 (Click for link to problem statements)

Nearest Delivery Drops

A depot sits at the origin (0, 0). Delivery stops are given as [x, y] points in points. You want the k stops closest to the depot by straight-line distance.

Return the k closest points in any order.

def k_closest(points, k):
    pass

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Heaps, Priority Queues, Top-K Elements, Euclidean Distance

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: How do we measure how close a stop is to the depot?

    • A: By straight-line (Euclidean) distance from the origin: sqrt(x^2 + y^2). Since the square root is monotonic, we can compare squared distances x^2 + y^2 instead and skip the sqrt entirely.

  • Q: Does the order of the returned points matter?

    • A: No. The problem says the k closest points can be returned in any order.

  • Q: Can we assume k is valid, and can ties occur?

    • A: Assume 1 <= k <= len(points). If two stops are equally distant, either may be chosen; any valid set of k closest points is acceptable.
HAPPY CASE
Input: points = [[1, 3], [-2, 2]], k = 1
Output: [[-2, 2]]
Explanation: The distance of [1, 3] from the depot is sqrt(10), while [-2, 2] is sqrt(8). Since sqrt(8) < sqrt(10), the single closest stop is [-2, 2].

Input: points = [[3, 3], [5, -1], [-2, 4]], k = 2
Output: [[3, 3], [-2, 4]]
Explanation: The squared distances are 18, 26, and 20. The two smallest are 18 ([3, 3]) and 20 ([-2, 4]), so those two stops are returned (in any order).

EDGE CASE
Input: points = [[0, 0]], k = 1
Output: [[0, 0]]
Explanation: A stop can sit exactly on the depot; its distance is 0 and it is trivially the closest.

Input: points = [[1, 2], [3, 4]], k = 2
Output: [[1, 2], [3, 4]]
Explanation: When k equals the number of stops, every stop is returned.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Top-K Elements Problems, we can consider the following approaches:

  • Max-Heap of Size K: Keep a heap of the k closest stops seen so far; whenever the heap grows past k, evict the farthest stop. Python's heapq is a min-heap, so we store negated distances to simulate a max-heap.
  • Sorting: Sort all stops by distance and take the first k. Simpler, but does more work than needed (O(N log N) instead of O(N log k)).

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Maintain a max-heap holding at most k stops, keyed on distance from the depot. For each stop, compute its squared distance and push it onto the heap; if the heap now holds more than k stops, pop the farthest one. After processing every stop, the heap contains exactly the k closest stops.

1) Initialize an empty heap.
2) For each point [x, y] in points:
   a) Compute the squared distance: dist = x^2 + y^2 (no sqrt needed for comparison).
   b) Push (-dist, [x, y]) onto the heap. Negating the distance turns Python's min-heap into a max-heap.
   c) If the heap size exceeds k, pop from the heap. This removes the entry with the largest distance seen so far.
3) Return the points remaining in the heap.

⚠️ Common Mistakes

  • Forgetting to negate the distance: heapq is a min-heap, so popping would evict the closest stop instead of the farthest.
  • Computing sqrt for every point. It is unnecessary for comparisons and introduces floating-point values where integers suffice.
  • Popping before pushing (or never capping the heap at k), so the heap ends up with the wrong number of points.
  • Returning the negated distances (or (dist, point) tuples) instead of just the points.

4: I-mplement

Implement the code to solve the algorithm.

import heapq

def k_closest(points, k):
    # Max-heap of at most k stops, keyed on negated squared distance
    heap = []
    for x, y in points:
        dist = x * x + y * y  # squared distance; sqrt is not needed to compare
        heapq.heappush(heap, (-dist, [x, y]))
        if len(heap) > k:
            heapq.heappop(heap)  # evict the farthest stop seen so far
    return [point for _, point in heap]

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Input: points = 1, 3], [-2, 2, k = 1

    • [1, 3]: dist = 1 + 9 = 10. Push (-10, [1, 3]). Heap size 1, no eviction.
    • [-2, 2]: dist = 4 + 4 = 8. Push (-8, [-2, 2]). Heap size 2 > 1, so pop (-10, [1, 3]) — the farthest stop.
    • Output: -2, 2

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

    • [3, 3]: dist = 18. Push (-18, [3, 3]).
    • [5, -1]: dist = 26. Push (-26, [5, -1]). Heap size 2, no eviction.
    • [-2, 4]: dist = 20. Push (-20, [-2, 4]). Heap size 3 > 2, so pop (-26, [5, -1]) — the farthest stop.
    • Output: -2, 4], [3, 3 (equivalent to 3, 3], [-2, 4 since any order is accepted)

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of delivery stops and k is the number of stops requested.

  • Time Complexity: O(N log k) because each of the N stops triggers at most one push and one pop on a heap that never exceeds k + 1 elements.
  • Space Complexity: O(k) for the heap holding the closest stops (ignoring the O(k) output list).

Clone this wiki locally