LC 1475. Final Prices with a Special Discount in a Shop

The problem

Solution - $O(n)$ Time

While similar to other monotonic stack problems, this one's input can have duplicates, which tripped me up from getting it right on the first submission. I wasn't reading the examples closely and put the prices directly in the stack. Then, by using indexOf, only the first appearance of a value is accessible.

In my second submission below, I store the indices of the original prices in the stack for greater specificity. These indices are used to check for decreasing or equal values that create discounts and when setting and calculating the resulting discounted prices.

Another detail to mention is that I deep-copy the original prices at the start and overwrite any that require discounts so that any values that weren't discounted are already in my result.

function finalPrices(prices: number[]): number[] {
  let ans = [...prices]
  let stack = []
  for (let i = 0; i < prices.length; i++) {
    while (stack.length && prices[i] <= prices[stack[stack.length - 1]]) {
      let priceIdx = stack.pop()
      ans[priceIdx] = prices[priceIdx] - prices[i]
    }
    stack.push(i)
  }

  return ans
}