Two gift prices that hit the budget exactly

Arrays, strings and hash maps Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Fill the blank

Fill the blank so a gift is never paired with itself.

Python 3.13
def gift_pair(prices: list[int], budget: int) -> list[int]:
    first_at: dict[int, int] = {}
    for j, p in enumerate(prices):
        ____
        if p not in first_at:
            first_at[p] = j
    return []
print(gift_pair([3, 4, 3], 6))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A if budget - p in first_at: return [first_at[budget - p], j]

Right: the lookup runs before the current price is stored, so index j can only pair with an earlier index.

With [3, 4, 3] and budget 6 the answer must be [0, 2]: the two different gifts priced 3, never gift 0 with itself.

Why not the others?
  • B first_at[p] = j. Storing first means the lookup can find the same gift when budget is twice its price.
  • C return [j, j]. That returns the same gift twice and ignores the budget.

30-second answer

Walk the prices once with a map from price to the first index where it appeared. For each price p at index j, look up budget - p: if it is in the map, that index and j are the answer. One pass, O(n) time and O(n) space, and the tie rule falls out of scanning left to right.

Practise saying it · 60 s. No recording, just a timer

Walk through the one-pass pair lookup and its tie rule.

Say your answer out loud, then check which of these points you covered:

  • Map of value to first index
  • Look up before insert
  • O(n) time, O(n) space

Deep dive

The map stores what you have already passed, so every lookup asks 'did a partner come before me?'. That is why one pass is enough.

Keep the first index of each price (if p not in first_at) so ties pick the earliest first gift.

If the list were sorted, two pointers from both ends would find a pair in O(n) time with O(1) space, but sorting first costs O(n log n) and loses the original indices.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def gift_pair(prices: list[int], budget: int) -> list[int]:
    first_at: dict[int, int] = {}
    for j, p in enumerate(prices):
        need = budget - p
        if need in first_at:
            return [first_at[need], j]
        if p not in first_at:
            first_at[p] = j
    return []

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun giftPair(prices: List<Int>, budget: Int): List<Int> {
    val firstAt = HashMap<Int, Int>()
    for ((j, p) in prices.withIndex()) {
        val i = firstAt[budget - p]
        if (i != null) return listOf(i, j)
        firstAt.putIfAbsent(p, j)
    }
    return emptyList()
}

Common mistakes

  • Inserting the current price before the lookup, which pairs a gift with itself when budget = 2 * price.
  • Returning prices instead of indices, or indices in the wrong order.

Senior take & follow-ups

The interview signal here is the order of operations: look up the complement, then insert. Say why, and test budget = 2 × price out loud.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if you need every pair, not one?

    Show hint

    Keep a count per price; the number of pairs grows with matches, so the output size bounds the time.

  2. What if the list is too big for memory?

    Show hint

    Sort on disk and sweep with two pointers, or partition by price range.

Similar on iOS: Hashable Swift needs your key type to conform to Hashable; Python hashes any immutable value, and lists are refused as keys.

What each operation costs: Arrays · Dynamic Arrays · Hash Table · Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.