You are given an integer array prices where prices[i] is the price of the ith item in a shop.

For each item i, find the smallest index j such that $j > i$ and prices[j] <= prices[i]. If such an index j exists, the discount for item i is prices[j], and the final price becomes prices[i] - prices[j]. If no such j exists, the final price for item i remains prices[i].

Return an array of the final prices for all items in the same order as prices.

Constraints:

• $1 \leq$ prices.length $\leq 500$

• $1 \leq$ prices[i] $\leq 1000$

Input: prices = [7, 5, 5, 6]-List[int]
Output: [2, 0, 5, 6]-List[int]
Explanation: For item 0 (7), the next price <= 7 is 5 at index 1, giving 7 - 5 = 2; for item 1 (5), the next price <= 5 is 5 at index 2, giving 5 - 5 = 0; item 2 (5) has no later price <= 5, so it stays 5; and item 3 (6) has no later items, so it stays 6.

Input: prices = [2, 9, 1, 8, 3]-List[int]
Output: [1, 8, 1, 5, 3]-List[int]
Explanation: For item 0 (2), the next price <= 2 is 1 at index 2, giving 2 - 1 = 1; for item 1 (9), it is 1 at index 2, giving 9 - 1 = 8; item 2 (1) has no later price <= 1, so it stays 1; for item 3 (8), the next price <= 8 is 3 at index 4, giving 8 - 3 = 5; and item 4 (3) has no later items, so it stays 3.

Input: prices = [6, 6, 6, 6]-List[int]
Output: [0, 0, 0, 6]-List[int]
Explanation: For items 0, 1, and 2 (6), the next price <= 6 is the 6 at the following index, giving 6 - 6 = 0 each, and item 3 (6) has no later items, so it stays 6.

Input: prices = [1000]-List[int]
Output: [1000]-List[int]
Explanation: There is only one item, so there is no later item to provide a discount, and the final price remains 1000.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.