Nearest Delivery Drops

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](/compsci/-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](/compsci/0,-0), k = 1
Output: [0, 0](/compsci/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).