1475. Final Prices With a Special Discount in a Shop

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

Approach 01:

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int totalItems = prices.size();
        for (int currentItem = 0; currentItem < totalItems - 1; currentItem++) {
            for (int nextItem = currentItem + 1; nextItem < totalItems; nextItem++) {
                if (nextItem > currentItem && prices[currentItem] >= prices[nextItem]) {
                    prices[currentItem] -= prices[nextItem];
                    break;
                }
            }
        }
        return prices;
    }
};

class Solution:
    def finalPrices(self, prices):
        totalItems = len(prices)
        for currentItem in range(totalItems - 1):
            for nextItem in range(currentItem + 1, totalItems):
                if nextItem > currentItem and prices[currentItem] >= prices[nextItem]:
                    prices[currentItem] -= prices[nextItem]
                    break
        return prices

Time Complexity

• Outer Loop:
  • The outer loop iterates over all items in the prices array, running \(n – 1\) times where \(n\) is the size of the array.
• Inner Loop:
  • For each iteration of the outer loop, the inner loop checks all subsequent items in the array.
  • In the worst case:
    • The first item checks \(n – 1\) items.
    • The second item checks \(n – 2\) items, and so on.
  • The total number of comparisons is the sum of the first \(n – 1\) integers, which is \(\frac{(n-1) \cdot n}{2} = O(n^2)\).
• Overall Time Complexity:

  The total time complexity is \(O(n^2)\), as the nested loops dominate the computation.

Space Complexity

• Input Array:
  • The input array prices is modified in place, requiring \(O(n)\) space for storage.
• Auxiliary Variables:
  • Integer variables (totalItems, currentItem, nextItem) are used for iteration and consume \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(n)\), dominated by the input array.