Final Prices With a Special Discount

EasyStackmonotonic stack

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A shop lists items in a row with prices prices[0..n-1]. Buying item i earns a discount equal to prices[j], where j is the **smallest index greater than i** with prices[j] <= prices[i]. If no such j exists, item i gets no discount. Return an array answer of length n where answer[i] is the price actually paid for item i. A simple O(n^2) scan works for the given limits; try for O(n) with a stack.

Examples

Input: prices = [10,7,9,7,3]
Output: [3,0,2,4,3]
Item 0 (10) is discounted by the 7 right after it. Item 1 (7) skips the 9 and is discounted by the next 7. Item 2 (9) gets 7 off, item 3 (7) gets 3 off, and the last item has no discount.
Input: prices = [1,2,3,4]
Output: [1,2,3,4]
Every later price is higher, so no item gets a discount.

Constraints

  • 1 <= prices.length <= 500
  • 1 <= prices[i] <= 1000

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More monotonic stack problems