Quiz — Hash Map Patterns

A list holds n prices and you have a budget. Find two different items whose prices add up to the budget exactly. Which approach does it in one pass, in O(n) time on average?

Put every price in a map, then look up the budget itself

Sort the prices, then binary search for budget − price for each one

For each price, look up budget − price among the prices seen so far, then record this price

Compare every price with every later price