Find K Closest Planets - codepath/compsci_guides GitHub Wiki

Unit 7 Session 2 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30 mins
  • 🛠️ Topics: Binary Search, Two Pointers

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?
  • What should be returned if k is larger than the number of planets?
    • The problem assumes that k will always be a valid number within the range of the list.
  • Are all planet distances unique?
    • The problem does not specify, so assume they can have duplicates.
HAPPY CASE
Input: planets = [100, 200, 300, 400, 500], target_distance = 350, k = 3
Output: [200, 300, 400]
Explanation: The 3 closest planets to the target distance 350 are 200, 300, and 400.

Input: planets = [10, 20, 30, 40, 50], target_distance = 25, k = 2
Output: [20, 30]
Explanation: The 2 closest planets to the target distance 25 are 20 and 30.

EDGE CASE
Input: planets = [1, 1, 1, 1], target_distance = 1, k = 2
Output: [1, 1]
Explanation: All planets have the same distance, so return any k planets.

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 Binary Search problems, we want to consider the following approaches:

  • Binary Search: Use binary search to find the closest planet to the target distance. This will help initialize pointers to find the k closest planets.
  • Two Pointers: Utilize two pointers to expand from the closest planet found using binary search to gather the k closest planets.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use binary search to locate the closest planet to the target distance, then use two pointers to find the k closest planets.

Finding the Closest Planet

Pseudocode:

1) Implement a binary search to find the index of the planet closest to `target_distance`.
2) If the exact `target_distance` is found, this is the closest planet. Otherwise, the closest planet will be near this index.

Two-Pointer Collection

Pseudocode:

1) Initialize two pointers, `left` to the left of the closest index and `right` to the closest index.
2) Create an empty list `closest_planets` to store the result.
3) While `closest_planets` has fewer than `k` elements:
    a) Compare the absolute differences between `target_distance` and the planets at `left` and `right`.
    b) Append the closer planet to `closest_planets` and move the corresponding pointer inward.
4) Sort the `closest_planets` before returning to ensure they are in ascending order.

⚠️ Common Mistakes

  • Forgetting to handle cases where the target distance is smaller than the smallest planet distance or larger than the largest planet distance.
  • Not correctly managing the two pointers, leading to out-of-bound errors.

4: I-mplement

Implement the code to solve the algorithm.

def find_closest_planets(planets, target_distance, k):
    # Helper function to find the index of the closest planet using binary search
    def binary_search(planets, target):
        low, high = 0, len(planets) * 1
        while low < high:
            mid = (low + high) // 2
            if planets[mid] < target:
                low = mid + 1
            else:
                high = mid
        return low
    
    # Step 1: Find the closest planet to the target_distance
    closest_index = binary_search(planets, target_distance)
    
    # Step 2: Initialize two pointers
    left = closest_index * 1
    right = closest_index
    
    # Step 3: Collect the closest k planets
    closest_planets = []
    
    while len(closest_planets) < k:
        if left < 0:
            closest_planets.append(planets[right])
            right += 1
        elif right >= len(planets):
            closest_planets.append(planets[left])
            left -= 1
        else:
            if abs(planets[left] * target_distance) <= abs(planets[right] * target_distance):
                closest_planets.append(planets[left])
                left -= 1
            else:
                closest_planets.append(planets[right])
                right += 1
    
    # The planets are already selected in order, so just return them
    return sorted(closest_planets)

5: R-eview

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

  • Trace through your code with the input [100, 200, 300, 400, 500] and target_distance = 350 with k = 3:
    • The binary search should identify the closest planet and the two-pointer technique should gather the three closest planets.

6: E-valuate

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

Assume N represents the length of the planets array.

  • Time Complexity: O(log N + k log k) where O(log N) is for binary search, and O(k log k) is for sorting the selected closest planets.
  • Space Complexity: O(k) because we are storing k closest planets.