Find two prices summing to a budget, earliest pair first
A gift shop has a “pick any two” deal: a customer enters an exact gift card balance, and the site suggests two different products whose prices add up to exactly that balance, so nothing is left on the card. Products are listed in the order the shop wants to promote them.
Implement findBudgetPair(prices, budget). It returns the indexes [i, j] of two different items with prices[i] + prices[j] === budget, or [] if no pair exists.
findBudgetPair(prices, budget) // => [i, j] with i < j, or []
Several pairs can match. Return the pair that is completed earliest when you read the list from left to right:
j (the later of the two indexes).j, pick the one with the smallest i.i < j. One item cannot be used twice, but two items with the same price can be paired.[] for an empty array, a single item, or when no pair works.prices.findBudgetPair([12, 30, 25, 18, 7], 37); // => [0, 2] 12 + 25 (also 30 + 7, but that pair ends at index 4)
findBudgetPair([5, 1, 4, 4], 9); // => [0, 2] both 4s pair with 5; index 2 comes first
findBudgetPair([3, 3, 6], 9); // => [0, 2] both 3s pair with the 6; take the smaller i
findBudgetPair([4, 1], 8); // => [] 4 cannot be used twice
findBudgetPair([4, 4], 8); // => [0, 1]
findBudgetPair([-3, 0, 8, 3], 5); // => [0, 2]