1475. Final Prices With a Special Discount in a Shop

Given an array prices where prices[i] is the price of the i-th item in a shop. There's a special discount for the item, which you will receive when you buy it: the discount will be equal to the cost of the next item later in the line which has a smaller or equal price than the current item. If there is no such item, you will not receive any discount at that time. Return an array where the i-th element is the final price you will pay for the i-th item of the shop considering the special discount.

To implement the solution, we need to iterate over each item in the prices array and for each item, check the subsequent items to find the first one that has a price less than or equal to the current item's price. The difference between the current item's price and this found price will be the discounted price. If no such item is found, the item price remains unaffected. We can achieve this with a simple nested loop:

1. Loop through each item in the prices array using a variable i.
2. For each i, loop through the subsequent items using another variable j.
3. If prices[j] < prices[i]=, apply the discount by setting finalPrices[i] to prices[i] - prices[j] and break the inner loop.
4. If no such j is found, finalPrices[i] remains prices[i].
5. Return the computed finalPrices array.

The time complexity of this solution is O(n²) where n is the number of items because, in the worst case, for each item, we might have to look at all remaining items. The space complexity is O(1) if we modify the prices array in place to save space, otherwise it is O(n) for storing the result in a new array.

Consider the array of prices = [8, 4, 6, 2, 3].

• For the price 8 at the first position, the first smaller price is 4 (at the second position), so the discounted price is 8-4 which is 4.
• For the price 4, the first smaller price is 2, so the discounted price is 4-2 which is 2.
• For the price 6, the first smaller price is 2, so the discounted price is 6-2 which is 4.
• For the price 2, there are no smaller prices later, so the price remains 2.
• For the price 3, there are no smaller prices later, so the price remains 3.

Thus, the final prices to be returned are = [4, 2, 4, 2, 3] =.

For this problem, no specific frameworks or well-known algorithms are directly applicable. However, similar techniques for optimizing array traversals like using stacks can be explored for related problems. See also stack-based solutions for "next greater element" problems in coding platforms.

2024-12-18 Final Prices With a Special Discount in a Shop - Submission Detail - LeetCode leetcode.com

Below is a general framework to solve the problem and a setup for unit testing using JavaScript.

/**
 * Computes the final prices with special discount.
 * @param {number[]} prices - Array of prices.
 * @return {number[]} Final prices taking into account the special discount.
 */
function finalPrices(prices) {
    // Helper function to display logs and tables if not in a restricted environment
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger!== 'undefined' ? () => {} : console.table;

    if (prices.length < 2) return prices;

    const result = [];
    for (let i = 0; i < prices.length - 1; i++) {
        let hasDiscount = false;
        for (let j = i + 1; j < prices.length; j++) {
            if (prices[i] >= prices[j]) {
                result.push(prices[i] - prices[j]);
                hasDiscount = true;
                break;
            }
        }
        if (!hasDiscount) {
            result.push(prices[i]);
        }
    }
    result.push(prices[prices.length - 1]);
    table(result);
    return result;
}

// Test cases
const testCases = [
    { prices: [8, 4, 6, 2, 3], expected: [4, 2, 4, 2, 3] },
    { prices: [1, 2, 3, 4, 5], expected: [1, 2, 3, 4, 5] },
    { prices: [10, 1, 1, 6], expected: [9, 0, 1, 6] },
    { prices: [5, 8, 3, 10, 1], expected: [2,5,2,9,1] },
    { prices: [9, 4, 9, 1, 3], expected: [5, 3, 8, 1, 3] }
];

testCases.forEach((test, index) => {
    const result = finalPrices(test.prices);
    console.log(`Test Case ${index + 1}: ${result.toString() === test.expected.toString() ? 'Passed' : 'Failed'}` +
    ` (Expected: [${test.expected}], Got: [${result}])`);
});