Remove items so any k prices stay under a threshold

Question: Remove items so any k prices stay under a threshold

Companies: Amazon

Difficulty: Easy

Problem statement

A store is planning a holiday promotion from a list of candidate items with known prices. Shoppers may pick any k items from whatever stays on the list, and the store wants every such group of k items to cost at most threshold in total.

Implement:

def reduce_gifts(prices: list[int], k: int, threshold: int) -> int

Return the minimum number of items to remove from prices so that the sum of any k remaining items is at most threshold. If fewer than k items remain, no group of k exists and the condition is satisfied.

Constraints

• 1 <= k <= n <= 10^5, where n = len(prices)
• 1 <= prices[i] <= 10^9
• 1 <= threshold <= 10^9

Example 1

prices = [8, 1, 5, 7, 2], k = 2, threshold = 9  ->  2

The most expensive pair is 8 + 7 = 15. Remove 8: the most expensive pair is now 7 + 5 = 12. Remove 7: the most expensive pair is 5 + 2 = 7, which fits. Two removals.

Example 2

prices = [10, 10, 10, 10], k = 1, threshold = 9  ->  4

Every single item is over the limit, so all four must go.

Approach

Restate the condition. "Every group of k remaining items costs at most threshold" is the same as "the k most expensive remaining items cost at most threshold". Any other group of k costs no more than the top k. If fewer than k items remain, there is no group of k, so the condition holds trivially.

Brute force. Try removing 0 items, then 1, then 2, and so on. For each count, try every subset to remove and check the top k of what is left. That is exponential. A smarter brute force fixes the count r and argues which r to remove (below), then re-sorts and re-sums the top k each time: O(n · k) after sorting. Say it out loud, then improve it.

Greedy: always remove the most expensive items. Suppose some optimal answer removes a set R of size r. Swap any removed cheap item for a kept expensive one. The kept multiset only gets cheaper element by element, so its top-k sum can only go down. Therefore removing the r largest prices is never worse than any other choice of r items. The answer is the smallest r such that, after dropping the r largest, the top k sum is within threshold.

Sliding window over the sorted array. Sort prices ascending. After dropping the r largest, the top k remaining are prices[n-r-k .. n-r-1], a window of length k. Start with r = 0 (the window is the last k items) and slide the window one step left per removal: subtract the item leaving on the right, add the item entering on the left. Stop at the first window whose sum is at most threshold. If no window fits, remove until only k - 1 items remain, which is n - k + 1 removals.

Invariant. Before checking removal count r, window equals the sum of prices[n-r-k .. n-r-1], the k largest of the items still kept. Sums can reach about 10^5 · 10^9 = 10^14; Python ints are fine, but in Java or C++ use a 64-bit type.

Monotonicity (for the binary-search follow-up). Each removal makes the window sum no larger, so "window fits" is monotone in r. That allows a binary search too, but the linear slide is already O(n) after sorting.

Code

from typing import List


def reduce_gifts(prices: List[int], k: int, threshold: int) -> int:
    """Minimum removals so that any k remaining items sum to <= threshold."""
    n = len(prices)
    if k <= 0:
        raise ValueError("k must be positive")
    if n < k:
        return 0  # no group of k exists

    s = sorted(prices)
    # Window = the k largest items still kept; start with nothing removed.
    window = sum(s[n - k:])
    removed = 0
    # While a full window of k items exists, check it, then drop the largest.
    while removed <= n - k:
        if window <= threshold:
            return removed
        right = n - 1 - removed          # largest kept item; remove it
        left = n - k - removed - 1       # next item entering the window
        window -= s[right]
        if left >= 0:
            window += s[left]
        removed += 1
    # Fewer than k items left: condition holds vacuously.
    return n - k + 1


def reduce_gifts_brute(prices: List[int], k: int, threshold: int) -> int:
    """Reference: try each removal count, dropping the r largest."""
    s = sorted(prices)
    for r in range(len(s) + 1):
        kept = s[: len(s) - r]
        if len(kept) < k or sum(kept[-k:]) <= threshold:
            return r
    return len(s)


if __name__ == "__main__":
    import random

    assert reduce_gifts([8, 1, 5, 7, 2], 2, 9) == 2      # keep [1,2,5]: 2+5=7
    assert reduce_gifts([4, 4, 4], 3, 12) == 0
    assert reduce_gifts([4, 4, 4], 3, 11) == 1
    assert reduce_gifts([10, 10, 10, 10], 1, 9) == 4     # every single item too big
    assert reduce_gifts([3, 9], 3, 1) == 0               # n < k
    assert reduce_gifts([6, 1, 1, 1], 2, 2) == 1
    for _ in range(2000):
        n = random.randint(1, 8)
        arr = [random.randint(1, 10) for _ in range(n)]
        k = random.randint(1, n)
        t = random.randint(1, 40)
        assert reduce_gifts(arr, k, t) == reduce_gifts_brute(arr, k, t), (arr, k, t)
    print("ok")

Complexity

• Sorting: O(n log n) time.
• Sliding the window: O(n) time; each step does one subtraction and at most one addition.
• Space: O(n) for the sorted copy (O(1) extra if sorting in place is allowed).
• With values bounded and small, a counting sort would make the whole thing O(n + maxPrice), but that does not apply at prices[i] ≤ 10^9.

Test cases

• prices = [8, 1, 5, 7, 2], k = 2, threshold = 9 → 2. Sorted [1, 2, 5, 7, 8]; top pairs: 7+8=15, 5+7=12, 2+5=7.
• prices = [4, 4, 4], k = 3, threshold = 12 → 0 (already fits exactly; the check is <=).
• prices = [4, 4, 4], k = 3, threshold = 11 → 1 (drop one; only 2 items remain, fewer than k).
• prices = [10, 10, 10, 10], k = 1, threshold = 9 → 4 (every single item is over the limit; remove all of them).
• prices = [3, 9], k = 3, threshold = 1 → 0 (n < k, nothing to check).
• prices = [6, 1, 1, 1], k = 2, threshold = 2 → 1 (drop the 6; 1+1=2 fits).
• k = n → answer is 0 if the total fits, otherwise 1.
• Large: n = 10^5, all prices 10^9, k = 10^5, threshold = 10^9 → 1; sums near 10^14 must not overflow.

Follow-ups

1. Return which items to remove, not just how many. Sort indices by price instead of values; the answer is the indices of the r largest. Ties can go either way, so say which one you pick (for example, the later index).
2. At most k items instead of exactly k. Prices are positive, so a smaller group always costs less than a bigger one that contains it. The condition is the same, and so is the code. If prices could be zero or negative, the top-m sum for m < k could be larger, so you check every prefix of the top k.
3. Stream of price updates (add or remove an item, then answer again). Keep the prices in a sorted structure (a sorted list or a balanced BST, or a Fenwick tree over compressed values with counts and sums). Binary-search the removal count r using "sum of the k largest after dropping r" as an O(log n) range-sum query: O(log² n) per query.
4. Many (k, threshold) queries on the same array. Sort once and build prefix sums. For each query, the window sum for removal count r is a prefix-sum difference, and it is monotone in r, so binary search: O(log n) per query after O(n log n) setup.
5. Each item has a removal cost; minimize total cost instead of count. The exchange argument breaks, because removing a cheap-to-remove mid-priced item may beat removing the most expensive one. Discuss the harder structure (it becomes a choice over which top-k survives) and fall back to DP or a priority-queue heuristic, and say that the simple greedy no longer holds.

Interviewer expectations

Mid-level (L4)

• Sees that only the k most expensive remaining items matter.
• Sorts and removes from the top, with a correct sliding window or prefix sums.
• Handles n < k, the <= boundary, and the "remove down to k - 1" case.

Senior (L5)

• Gives a clean exchange argument for why removing the largest items is optimal.
• Writes an O(n log n) solution in one pass and mentions 64-bit sums.
• Checks against a brute force or small hand traces without being asked.

Staff (L6+)

• Moves to many queries or updates (prefix sums plus binary search, Fenwick tree) and states the monotonicity that makes it work.
• Says exactly where the greedy breaks (non-positive prices, weighted removal costs) and what replaces it.
• Keeps the code short and the invariant explicit, and talks through the trade-offs clearly.