Final Prices With a Special Discount in a Shop

Final Prices With a Special Discount in a Shop is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Monotonic Stack subpattern.

Problem statement

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

There is a special discount for items in the shop. If you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i]. Otherwise, you will not receive any discount at all.

Return an integer array answer where answer[i] is the final price you will pay for the ith item of the shop, considering the special discount.

Example 1:

Input: prices = [8,4,6,2,3] Output: [4,2,4,2,3] Explanation: For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4. For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2. For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4. For items 3 and 4 you will not receive any discount at all.

Example 2:

Input: prices = [1,2,3,4,5] Output: [1,2,3,4,5] Explanation: In this case, for all items, you will not receive any discount at all.

Example 3:

Input: prices = [10,1,1,6] Output: [9,0,1,6]

Constraints:

- 1 <= prices.length <= 500

- 1 <= prices[i] <= 1000

Topics and companies

Topics: Array, Stack, Monotonic Stack.

Reported in interviews at Dream11.

How to practise Final Prices With a Special Discount in a Shop on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Final Prices With a Special Discount in a Shop in the code editor, or read the Final Prices With a Special Discount in a Shop editorial for a worked solution with its approach and complexity analysis.

Where Final Prices With a Special Discount in a Shop sits in the DSA pattern sheet

Problems related to Final Prices With a Special Discount in a Shop

Other problems that use the same Monotonic Stack and Stack Patterns techniques:

Preparing this workspace.