Welcome to Subscribe On Youtube

1475. Final Prices With a Special Discount in a Shop

Description

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

Solutions

  • class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = prices[i];
            for (int j = i + 1; j < n; ++j) {
                if (prices[j] <= prices[i]) {
                    ans[i] -= prices[j];
                    break;
                }
            }
        }
        return ans;
    }
}

  • class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        int n = prices.size();
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            ans[i] = prices[i];
            for (int j = i + 1; j < n; ++j) {
                if (prices[j] <= prices[i]) {
                    ans[i] -= prices[j];
                    break;
                }
            }
        }
        return ans;
    }
};

  • class Solution:
    def finalPrices(self, prices: List[int]) -> List[int]:
        ans = []
        for i, v in enumerate(prices):
            ans.append(v)
            for j in range(i + 1, len(prices)):
                if prices[j] <= v:
                    ans[-1] -= prices[j]
                    break
        return ans


  • func finalPrices(prices []int) []int {
	n := len(prices)
	ans := make([]int, n)
	for i, v := range prices {
		ans[i] = v
		for j := i + 1; j < n; j++ {
			if prices[j] <= v {
				ans[i] -= prices[j]
				break
			}
		}
	}
	return ans
}

  • function finalPrices(prices: number[]): number[] {
    const n = prices.length;
    const ans = new Array(n);
    for (let i = 0; i < n; ++i) {
        ans[i] = prices[i];
        for (let j = i + 1; j < n; ++j) {
            if (prices[j] <= prices[i]) {
                ans[i] -= prices[j];
                break;
            }
        }
    }
    return ans;
}


  • /**
 * @param {number[]} prices
 * @return {number[]}
 */
var finalPrices = function (prices) {
    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            if (prices[i] >= prices[j]) {
                prices[i] -= prices[j];
                break;
            }
        }
    }
    return prices;
};


  • class Solution {
    /**
     * @param Integer[] $prices
     * @return Integer[]
     */
    function finalPrices($prices) {
        for ($i = 0; $i < count($prices); $i++) {
            for ($j = $i + 1; $j < count($prices); $j++) {
                if ($prices[$i] >= $prices[$j]) {
                    $prices[$i] -= $prices[$j];
                    break;
                }
            }
        }
        return $prices;
    }
}


  • impl Solution {
    pub fn final_prices(prices: Vec<i32>) -> Vec<i32> {
        let n = prices.len();
        let mut stack = Vec::new();
        let mut res = vec![0; n];
        for i in (0..n).rev() {
            let price = prices[i];
            while !stack.is_empty() && *stack.last().unwrap() > price {
                stack.pop();
            }
            res[i] = price - stack.last().unwrap_or(&0);
            stack.push(price);
        }
        res
    }
}

All Problems

All Solutions