Reach a Promotion Threshold from a Cart

Updated · By

Work out how much the cart still needs. Sort the prices; a binary search finds the cheapest single item that covers the gap. If none does, two pointers from both ends find the cheapest pair: move the right pointer in while the pair qualifies, otherwise move the left one up. O(n log n) for the sort, linear after it.

mediumPattern: Two pointersFrom Devana's Amazon question set

Problem

A promotion applies once a cart's total reaches a threshold. The customer is short, and you want to suggest something from items they recently viewed that would get them over it for as little extra as possible.

Write suggest_topup(cart_total, threshold, candidates). Suggest the cheapest single candidate that brings the total to at least the threshold. If no single item is enough, suggest the cheapest pair of items that is. Return the suggestion as a list of prices sorted ascending, or an empty list when nothing is needed or nothing works.

def suggest_topup(cart_total: int, threshold: int, candidates: list[int]) -> list[int]:

This is one of Devana's own questions, written in the style of Amazon's interviews. It is not a question leaked from Amazon, and Devana is not affiliated with Amazon.

Constraints

  • Prices are positive whole numbers. Candidates may repeat, and a pair uses two different items.
  • A qualifying single item is always preferred to a pair.
  • Among pairs with the same total, the one with the cheaper first item wins.
  • Return [] when the cart already meets the threshold, or when no item or pair reaches it.
  • Up to 10^5 candidates.

Examples

Example 1

Input:  cart_total = 40, threshold = 50, candidates = [15, 8, 20]
Output: [15]

The cart needs 10 more. 8 is the cheapest item but only reaches 48; 15 is the cheapest item that gets there.

Example 2

Input:  cart_total = 40, threshold = 50, candidates = [3, 4, 6]
Output: [4, 6]

No single item covers the 10 needed, and 4 + 6 is the only pair that does.

Hints

Open one at a time, and try the problem again after each.

Hint 1

Turn it into one number: need = threshold - cart_total. If it is zero or less, you are done.

Hint 2

In a sorted list, the cheapest single item that covers need is the first price at or above it. That is a binary search.

Hint 3

For the pair, put one pointer on the cheapest price and one on the most expensive. If their sum reaches need, record it and try a cheaper right side. If it falls short, the left price is too small for any partner still in range, so move it up.

Hint 4

Record a pair only when its total is strictly lower than the best so far, and the tie-break takes care of itself.

Approach: from brute force to optimal

Brute force

Check every item for the single, then every pair with two nested loops, keeping the cheapest qualifying total.

Complexity: O(n²) time, O(1) extra space

Sort, binary search, then two pointers

Sorting once makes both questions easy. The single is bisect_left(prices, need): if that index is inside the list, the price there is the answer. Otherwise every price is below need and you look for a pair.

Start with lo at the cheapest price and hi at the most expensive. When the pair reaches need, it is a candidate, and the only way to find a cheaper qualifying pair with this lo is a smaller hi, so move hi down. When it falls short, prices[lo] cannot reach need with any partner at or below hi, so move lo up. Every step discards one price for good, which makes the walk linear.

Complexity: O(n log n) for the sort, O(log n) for the single, O(n) for the pair walk; O(n) for the sorted copy

How to say it in the interview

Reduce the problem to need out loud, then say why sorting helps both halves: the single is a binary search, and the pair is a two pointer walk where every step rules out one price. List the edge cases before coding: already over the threshold, nothing reaches it, and a pair of equal prices.

Solution

Python

from bisect import bisect_left

def suggest_topup(cart_total, threshold, candidates):
    need = threshold - cart_total
    if need <= 0:
        return []
    prices = sorted(candidates)

    # The cheapest single item that covers the gap.
    i = bisect_left(prices, need)
    if i < len(prices):
        return [prices[i]]

    # The cheapest pair: every step discards one price for good.
    best = None
    lo, hi = 0, len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total >= need:
            if best is None or total < sum(best):
                best = [prices[lo], prices[hi]]
            hi -= 1        # look for a cheaper partner for prices[lo]
        else:
            lo += 1        # prices[lo] is too small for any partner left
    return best or []

JavaScript

function suggestTopup(cartTotal, threshold, candidates) {
  const need = threshold - cartTotal;
  if (need <= 0) return [];
  const prices = [...candidates].sort((a, b) => a - b);

  // The cheapest single item that covers the gap: the first price >= need.
  let left = 0, right = prices.length;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (prices[mid] < need) left = mid + 1;
    else right = mid;
  }
  if (left < prices.length) return [prices[left]];

  // The cheapest pair: every step discards one price for good.
  let best = null;
  let lo = 0, hi = prices.length - 1;
  while (lo < hi) {
    const total = prices[lo] + prices[hi];
    if (total >= need) {
      if (best === null || total < best[0] + best[1]) best = [prices[lo], prices[hi]];
      hi--; // look for a cheaper partner for prices[lo]
    } else {
      lo++; // prices[lo] is too small for any partner left
    }
  }
  return best ?? [];
}

Both versions are tested against the same cases, including every example on this page.

  • JavaScript's default sort compares numbers as strings, so the comparator is required.
  • lo < hi keeps the pointers on two different items, so a pair of equal prices such as [5, 5] works only when that price really appears twice.
  • Recording only strictly cheaper totals gives ties to the pair with the cheaper first item, because lo only moves up.

Follow-up questions

Generalize to k items. Why does that become much harder?

The cheapest subset whose sum reaches a target is a knapsack problem. For a small fixed k you can extend the pointer idea, fixing one item and solving for k minus 1, at about O(n^(k-1)); in general it is a dynamic program over totals, pseudo-polynomial in the prices.

Should a cheaper pair beat a single item?

Not in this version: one added item is the simpler suggestion. If the business prefers the lowest total, compare the best single with the best pair; both are already computed, so it costs nothing extra.

What if some items are excluded from the promotion?

Filter them out before sorting. If the cart total itself only counts eligible items, compute need from the eligible total as well.

How would you rank suggestions by likelihood of purchase rather than price?

Keep the price walk as the filter for what qualifies, then score the qualifying items by predicted purchase probability and suggest the best one.

Common mistakes

  • Returning the cheapest item overall instead of the cheapest one that covers the gap.
  • Pairing an item with itself when it appears only once.
  • Sorting numbers with JavaScript's default sort.
  • Forgetting the case where the cart already meets the threshold.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Practice this problem out loud

Josh, Devana's AI interviewer, runs this exact problem as a voice mock interview, asks follow-ups like the ones above, and scores you out of 100. The Free plan has 3 interviews a month, no card needed.

Practice this problem in a mock interview