Leetcode 1475: Final Prices With a Special Discount in a Shop

In this Leetcode problem, we want to find the real prices of items given a special discount rule.

Problem statement

Solution

A couple of ideas for the solution:

1. Create a new array res to hold the result of the method (we could very well use the input array too, and there is no problem doing that)
2. For each item i look for the index j corresponding to the discount, if it exists, by checking all the indices after i, and picking the first one for which the rule prices[j] ≤ prices[i] applies.
3. If we found j apply the discount in the array res
4. When all is done, return the res array.

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

This algorithm is O(n²) in time, beats 100% of the Java solutions.

Submission results

Happy coding!

What’s next:

• Checkout the solution for another problem: Rearrange words in a sentence
• Contact me: poitevinpm@gmail.com
• Looking to interview for a software engineer position? Contact me :)