Compute final prices with next smaller discount

Q: Compute final prices with next smaller discount

This question evaluates array-processing and algorithmic problem-solving skills, focusing on reasoning about subsequent elements to compute element-wise discounts under input constraints.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an integer array prices of length n, where prices[i] is the original price of the i-th item.

For each item i, find the first index j > i such that prices[j] <= prices[i]. That prices[j] becomes the discount for item i, so the final price of item i is:

prices[i] - prices[j] if such j exists
otherwise prices[i]

Return an array finalPrices of length n containing the final price for each item.

Input

prices : array of integers

Output

finalPrices : array of integers

Example

Input: prices = [8, 4, 6, 2, 3]
Output: [4, 2, 4, 2, 3]

Constraints (typical)

1 <= n <= 2e5
1 <= prices[i] <= 1e9

Compute final prices with next smaller discount

Quick Overview

Input

Output

Example

Constraints (typical)

Comments (0)