FastPrep
Problem · Array

Final Price Discount

Learn this problem
● EasyMicrosoft logoMicrosoftINTERNNEW GRADOA
See Microsoft hiring insights

Problem statement

Given an array of product prices prices, compute the final price of every product.

For the product at index i, find the smallest index j such that j > i and prices[j] <= prices[i]. If such an index exists, use prices[j] as the discount and set the final price to prices[i] - prices[j]. If no such index exists, keep prices[i] unchanged.

Return the final prices in the original item order.

Function

finalPrices(prices: int[]) → int[]

Examples

Example 1

prices = [8,4,6,2,3]return = [4,2,4,2,3]

The first eligible prices to the right are 4 for price 8, 2 for price 4, and 2 for price 6. The last two products have no eligible price to their right.

Example 2

prices = [5,5,3,6]return = [0,2,3,6]

The second price 5 is the first eligible discount for the first product, so equality is allowed and its final price is 0. The next product uses price 3 as its discount. Prices 3 and 6 remain unchanged.

Constraints

  • 1 <= prices.length <= 100000
  • 1 <= prices[i] <= 1000000000

More Microsoft problems

drafts saved locally
public int[] finalPrices(int[] prices) {
    // write your code here
}
prices[8,4,6,2,3]
expected[4,2,4,2,3]
checking account