Overflowing with Gold - codepath/compsci_guides GitHub Wiki

U-nderstand

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

• Q
  • What is the desired outcome?
    • To find the indices of two distinct locations such that the sum of the gold amounts at these locations equals the target.
  • What input is provided?
    • An array gold_amounts of integers representing the gold amounts at each location, and an integer target.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a hashmap to keep track of the indices of gold amounts as we iterate through the list. For each gold amount, calculate the complement (the amount needed to reach the target) and check if it has already been seen.

1) Initialize an empty dictionary `gold_map` to store the gold amounts and their corresponding indices.
2) Iterate through the `gold_amounts` array using an index `i`:
   - Calculate the complement of the current gold amount (`target - amount`).
   - If the complement exists in `gold_map`, return the indices of the complement and the current location.
   - Otherwise, store the current gold amount with its index in `gold_map`.
3) If no solution is found by the end of the loop, return an empty list (though the problem assumes there is exactly one solution).

⚠️ Common Mistakes

• Forgetting that each input has exactly one solution.
• Accidentally using the same location twice instead of distinct locations.

I-mplement

def find_treasure_indices(gold_amounts, target):
    gold_map = {}
    for i, amount in enumerate(gold_amounts):
        complement = target - amount
        if complement in gold_map:
            return [gold_map[complement], i]
        gold_map[amount] = i
    return []