Reduce Gifts

Problem Overview

• Find the minimum number of items to remove so the sum of any k prices in the list never exceeds a given threshold.
• Input: prices array, k, threshold; output: minimum removals; if number of items < k, return 0.
• Constraints: 1 ≤ k ≤ n ≤ 1e5, 1 ≤ threshold ≤ 1e9, prices[i] ∈ [1,100].
• Real-world context: Amazon sale planning, trimming a product list to control the cost of any k chosen items.
• Asked in Amazon interviews; a coding interview problem and common interview question.