Final Prices With a Special Discount in a Shop solution and explanation
Google
9 more videos on this problem
Final Prices With a Special Discount in a Shop - Leetcode 1475 - PythonNeetCodeIO · 10:24 · 9K views
Final Prices With a Special Discount in a Shop | Something to learn |Leetcode 1475 |codestorywithMIKcodestorywithMIK · 24:21 · 5K views
LeetCode 1475: Final Prices With a Special Discount in a ShopEngineering Digest · 5:21 · 1K views
Final Prices With a Special Discount in a Shop | Leetcode 1475Techdose · 14:33 · 1K views
1475. Final Prices With a Special Discount in a Shop | Monotonic Stack | 2 ApproachesAryan Mittal · 13:58 · 1K views
1475. Final Prices With a Special Discount in a Shop | leetcode daily challenge | shashcode30ShashCode · 12:47 · 1K views
LeetCode 1475. Final Prices With a Special Discount in a Shop Solution Explained - JavaAlgorithms and Data Structures Course · 13:19 · 905 views
leetcode - 1475 Final Prices With a Special Discount in a Shop with ExplanationlitCode · 13:19 · 864 views
1475. Final Prices With a Special Discount in a Shop | Daily Challenge | 18 Dec 2024CTO Bhaiya · 15:39 · 677 views
1475 Final Prices With a Special Discount in a Shop | leetcode Easy Level Question Complete PlaylistEduEverybody · 9:02 · 596 views
The problem
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 <= 5001 <= prices[i] <= 1000
Approach overview
Problem Overview: You receive an array prices where each element represents the price of an item in a shop. For every item i, you must find the first item to its right with price less than or equal to prices[i]. That value becomes the discount applied to item i. If no such item exists, the price stays the same. Return the array of final prices.
Approach 1: Brute Force Scan (O(n²) time, O(1) space)
The direct strategy checks every element to the right of each item. For index i, iterate from i + 1 to the end of the array until you find the first value <= prices[i]. Subtract that value and stop searching for that index. If no qualifying value appears, keep the original price. This approach uses simple nested loops and no additional data structures. It works well for small arrays and clearly demonstrates the rule of “first smaller-or-equal value to the right,” but the quadratic time complexity becomes inefficient as n grows.
Approach 2: Monotonic Stack (O(n) time, O(n) space)
The optimal solution uses a decreasing monotonic stack to track indices whose discounts have not been found yet. Traverse the array from left to right. While the stack is not empty and the current price is less than or equal to the price at the index on top of the stack, the current price becomes the discount for that index. Pop the index and subtract the discount from its price. Then push the current index onto the stack.
This works because the stack maintains indices in strictly increasing price order. Once a smaller or equal value appears, it resolves the discount for all higher prices waiting in the stack. Each index is pushed and popped at most once, giving linear time complexity. The pattern is common in stack-based problems that ask for the “next smaller element.”
Using a monotonic structure avoids repeated scanning and ensures every comparison contributes to resolving a discount. The same pattern appears in problems like Next Smaller Element, Daily Temperatures, and Stock Span.
Recommended for interviews: Start by describing the brute force idea to show you understand the rule: find the first smaller-or-equal value to the right. Then move to the monotonic stack optimization. Interviewers typically expect the O(n) solution using a array traversal and stack because it demonstrates pattern recognition and efficient use of data structures.
Approach 1: Brute Force Approach
This approach involves checking each item's price and looking for the first subsequent item that has a lesser or equal price. We will iterate through the prices array and for each price, find the discount by iterating from the current index to the end of the array.
def finalPrices(prices):
result = list(prices)
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
if prices[j] <= prices[i]:
result[i] = prices[i] - prices[j]
break
return result
prices = [8, 4, 6, 2, 3]
print(finalPrices(prices))public class Solution {
public int[] finalPrices(int[] prices) {
int n = prices.length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
result[i] = prices[i];
for (int j = i + 1; j < n; j++) {
if (prices[j] <= prices[i]) {
result[i] = prices[i] - prices[j];
break;
}
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] prices = {8, 4, 6, 2, 3};
int[] result = sol.finalPrices(prices);
for (int price : result) {
System.out.print(price + " ");
}
}
}#include <vector>
#include <iostream>
std::vector<int> finalPrices(std::vector<int>& prices) {
int n = prices.size();
std::vector<int> result = prices;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (prices[j] <= prices[i]) {
result[i] = prices[i] - prices[j];
break;
}
}
}
return result;
}
int main() {
std::vector<int> prices = {8, 4, 6, 2, 3};
std::vector<int> result = finalPrices(prices);
for (int i : result) {
std::cout << i << " ";
}
return 0;
}function finalPrices(prices) {
let result = prices.slice();
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
if (prices[j] <= prices[i]) {
result[i] = prices[i] - prices[j];
break;
}
}
}
return result;
}
let prices = [8, 4, 6, 2, 3];
console.log(finalPrices(prices));#include <stdio.h>
void finalPrices(int* prices, int pricesSize, int* result) {
for (int i = 0; i < pricesSize; i++) {
result[i] = prices[i];
for (int j = i + 1; j < pricesSize; j++) {
if (prices[j] <= prices[i]) {
result[i] = prices[i] - prices[j];
break;
}
}
}
}
int main() {
int prices[] = {8, 4, 6, 2, 3};
int pricesSize = sizeof(prices) / sizeof(prices[0]);
int result[pricesSize];
finalPrices(prices, pricesSize, result);
for (int i = 0; i < pricesSize; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
public class Solution {
public int[] FinalPrices(int[] prices) {
int n = prices.Length;
int[] result = new int[n];
Array.Copy(prices, result, n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (prices[j] <= prices[i]) {
result[i] = prices[i] - prices[j];
break;
}
}
}
return result;
}
public static void Main() {
int[] prices = {8, 4, 6, 2, 3};
Solution solution = new Solution();
int[] result = solution.FinalPrices(prices);
Console.WriteLine(String.Join(" ", result));
}
}The Python solution uses lists to naturally handle the final prices. The structure of the code employs nested loops to check and apply the discounts sequentially through the price list.
Time Complexity: O(n^2) because each price may need to be compared to all subsequent prices in the worst case.
Space Complexity: O(n) to store the discounted prices.
Approach 2: Using Monotonic Stack
This optimized approach leverages a stack to efficiently track and find the next lower or equal price for each item. By using a stack, we can achieve the required result in linear time, processing each price only once while maintaining potential discounts.
def finalPrices(prices):
stack = []
result = prices[:]
for i in range(len(prices)):
while stack and prices[stack[-1]] >= prices[i]:
result[stack.pop()] -= prices[i]
stack.append(i)
return result
prices = [8, 4, 6, 2, 3]
print(finalPrices(prices))import java.util.Stack;
public class Solution {
public int[] finalPrices(int[] prices) {
Stack<Integer> stack = new Stack<>();
int n = prices.length;
int[] result = prices.clone();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && prices[stack.peek()] >= prices[i]) {
result[stack.pop()] = prices[stack.peek()] - prices[i];
}
stack.push(i);
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] prices = {8, 4, 6, 2, 3};
int[] result = solution.finalPrices(prices);
for (int price : result) {
System.out.print(price + " ");
}
}
}#include <vector>
#include <stack>
#include <iostream>
std::vector<int> finalPrices(std::vector<int>& prices) {
std::stack<int> stack;
int n = prices.size();
std::vector<int> result = prices;
for (int i = 0; i < n; ++i) {
while (!stack.empty() && prices[stack.top()] >= prices[i]) {
result[stack.top()] = prices[stack.top()] - prices[i];
stack.pop();
}
stack.push(i);
}
return result;
}
int main() {
std::vector<int> prices = {8, 4, 6, 2, 3};
std::vector<int> result = finalPrices(prices);
for (int price : result) {
std::cout << price << " ";
}
return 0;
}function finalPrices(prices) {
let result = prices.slice();
let stack = [];
for (let i = 0; i < prices.length; i++) {
while (stack.length && prices[stack[stack.length - 1]] >= prices[i]) {
let index = stack.pop();
result[index] -= prices[i];
}
stack.push(i);
}
return result;
}
let prices = [8, 4, 6, 2, 3];
console.log(finalPrices(prices));#include <stdio.h>
#include <stdlib.h>
void finalPrices(int* prices, int pricesSize, int* result) {
int* stack = (int*)malloc(pricesSize * sizeof(int));
int stackTop = -1;
for (int i = 0; i < pricesSize; i++) {
while (stackTop != -1 && prices[stack[stackTop]] >= prices[i]) {
int index = stack[stackTop--];
result[index] = prices[index] - prices[i];
}
stack[++stackTop] = i;
}
while (stackTop != -1) {
int index = stack[stackTop--];
result[index] = prices[index];
}
free(stack);
}
int main() {
int prices[] = {8, 4, 6, 2, 3};
int pricesSize = sizeof(prices) / sizeof(prices[0]);
int result[pricesSize];
finalPrices(prices, pricesSize, result);
for (int i = 0; i < pricesSize; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] FinalPrices(int[] prices) {
Stack<int> stack = new Stack<int>();
int[] result = (int[])prices.Clone();
for (int i = 0; i < prices.Length; i++) {
while (stack.Count > 0 && prices[stack.Peek()] >= prices[i]) {
result[stack.Pop()] -= prices[i];
}
stack.Push(i);
}
return result;
}
public static void Main() {
int[] prices = {8, 4, 6, 2, 3};
Solution solution = new Solution();
int[] result = solution.FinalPrices(prices);
Console.WriteLine(String.Join(" ", result));
}
}Python's implementation uses lists to handle stacks and directly adjust pricing. The monotonic stack keeps all elements being processed. Once a smaller or equal price is found, the results are updated accordingly.
Time Complexity: O(n) for processing each price once due to the stack constraint.
Space Complexity: O(n), since the stack may hold up to all indices.
Approach 3: Monotonic Stack
The problem is essentially to find the first element on the right side that is smaller than each element. We can use a monotonic stack to solve this.
We traverse the array prices in reverse order, using the monotonic stack to find the nearest smaller element on the left side of the current element, and then calculate the discount.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array prices.
function finalPrices(prices: number[]): number[] {
const stk: number[] = [];
for (let i = prices.length - 1; ~i; --i) {
const x = prices[i];
while (stk.length && stk.at(-1)! > x) {
stk.pop();
}
prices[i] -= stk.at(-1) || 0;
stk.push(x);
}
return prices;
}func finalPrices(prices []int) []int {
stk := []int{}
for i := len(prices) - 1; i >= 0; i-- {
x := prices[i]
for len(stk) > 0 && stk[len(stk)-1] > x {
stk = stk[:len(stk)-1]
}
if len(stk) > 0 {
prices[i] -= stk[len(stk)-1]
}
stk = append(stk, x)
}
return prices
}impl Solution {
pub fn final_prices(mut prices: Vec<i32>) -> Vec<i32> {
let mut stk: Vec<i32> = Vec::new();
for i in (0..prices.len()).rev() {
let x = prices[i];
while !stk.is_empty() && x < *stk.last().unwrap() {
stk.pop();
}
if let Some(&top) = stk.last() {
prices[i] -= top;
}
stk.push(x);
}
prices
}
}class Solution {
/**
* @param Integer[] $prices
* @return Integer[]
*/
function finalPrices($prices) {
$stk = [];
$n = count($prices);
for ($i = $n - 1; $i >= 0; $i--) {
$x = $prices[$i];
while (!empty($stk) && $x < end($stk)) {
array_pop($stk);
}
if (!empty($stk)) {
$prices[$i] -= end($stk);
}
$stk[] = $x;
}
return $prices;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) because each price may need to be compared to all subsequent prices in the worst case. |
| Using Monotonic Stack | Time Complexity: O(n) for processing each price once due to the stack constraint. |
| Monotonic Stack | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n²) | O(1) | Useful for understanding the rule or when the input size is very small. |
| Monotonic Stack | O(n) | O(n) | Best general solution. Efficient for large arrays and common in next-smaller-element problems. |
Frequently asked questions
Is Final Prices With a Special Discount in a Shop easy or hard?
The problem is classified as Easy on LeetCode with a high acceptance rate around 84%. Difficulty mainly comes from recognizing the monotonic stack pattern that efficiently finds the next smaller-or-equal element.
Final Prices With a Special Discount in a Shop Python/Java solution
Most implementations iterate through the price array and maintain a stack of indices. Python typically uses a list as a stack, while Java uses Stack or ArrayDeque. Both versions implement the same O(n) monotonic stack logic.
How to solve Final Prices With a Special Discount in a Shop in O(n)?
Use a monotonic stack that stores indices of prices. Iterate through the array and compare the current price with the price at the index on top of the stack. When the current price is smaller or equal, pop that index and apply the discount. Each element is processed once, resulting in O(n) time complexity.
What is the best approach for Final Prices With a Special Discount in a Shop?
The most efficient approach uses a monotonic decreasing stack. Traverse the array once and keep indices whose discounts have not been determined yet. When a smaller or equal price appears, it resolves the discount for elements in the stack. This method runs in O(n) time with O(n) auxiliary space.
Is Final Prices With a Special Discount in a Shop asked at Google/Amazon/Meta?
The problem itself appears frequently in interview preparation lists and coding platforms because it tests the monotonic stack pattern. Variations of next smaller element problems are commonly asked at companies such as Amazon, Google, and Meta.
What data structure is used in Final Prices With a Special Discount in a Shop?
The optimal approach uses a stack, specifically a monotonic decreasing stack that stores indices of items waiting for a discount. The array structure is used for the input and result, while the stack efficiently tracks unresolved prices.
What is the time complexity of Final Prices With a Special Discount in a Shop?
The optimal monotonic stack solution runs in O(n) time because each index is pushed and popped from the stack at most once. A straightforward brute force solution requires O(n²) time since it scans all elements to the right for every index.