Compute discounted prices in a queue
Company: Plaid
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given an integer array prices where prices[i] is the price of the i-th item in a checkout line, apply the following rule: for each i, find the first j > i such that prices[j] <= prices[i]; if such j exists, the item's discount is prices[j], so its final price is prices[i] - prices[j]; otherwise, no discount applies. Return both
(
1) the array of final prices and
(
2) the total savings across all items. Solve in O(n) time using an appropriate data structure, prove correctness, analyze time/space complexity, and provide code in a language of your choice along with brief tests.
Quick Answer: This question evaluates proficiency in array processing, algorithm design, use of auxiliary data structures such as monotonic stacks, and formal complexity and correctness reasoning.
You are given an integer array prices where prices[i] is the price of the i-th item in a checkout line. For each item i, find the first index j > i such that prices[j] <= prices[i]. If such a j exists, the discount for item i is prices[j], so its final price becomes prices[i] - prices[j]. Otherwise, the item keeps its original price. Return both: (1) the array of final prices for all items, and (2) the total savings across all items. Your solution should run in O(n) time using an appropriate data structure. A strong explanation should justify why the chosen data structure always finds the first valid discount for each item.
Constraints
- 0 <= len(prices) <= 200000
- 0 <= prices[i] <= 1000000000
Examples
Input: ([8, 4, 6, 2, 3],)
Expected Output: ([4, 2, 4, 2, 3], 8)
Explanation: Item 8 gets discount 4, item 4 gets discount 2, item 6 gets discount 2, and the last two items get no discount. Total savings are 4 + 2 + 2 = 8.
Input: ([1, 2, 3, 4, 5],)
Expected Output: ([1, 2, 3, 4, 5], 0)
Explanation: No item has a later price that is smaller than or equal to it, so no discounts apply.
Input: ([10, 1, 1, 6],)
Expected Output: ([9, 0, 1, 6], 2)
Explanation: 10 is discounted by the first 1, the second item 1 is discounted by the next 1, and the remaining two items receive no discount.
Input: ([5],)
Expected Output: ([5], 0)
Explanation: A single item has no later item, so it cannot receive a discount.