Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Final Prices With a Special Discount in a Shop
Bookmark
Brute Force
Monotonic Stack
Input
Input 1
Input 2
Input 3
Custom
prices
=
[8, 4, 6, 2, 3]
prices
8
0
4
1
6
2
2
3
3
4
result
prices
8
0
4
1
6
2
2
3
3
4
result
prices
8
0
4
1
6
2
2
3
3
4
i
result
item
8
: find the first price to its right that is
≤ it
prices
-4
8
0
4
1
6
2
2
3
3
4
j
i
result
4
4
≤ 8 → result[0] = 8 - 4 =
4
prices
8
0
4
1
6
2
2
3
3
4
j
i
result
4
6
> 4 → keep scanning
prices
-2
8
0
4
1
6
2
2
3
3
4
j
i
result
4
2
2
≤ 4 → result[1] = 4 - 2 =
2
prices
-2
8
0
4
1
6
2
2
3
3
4
j
i
result
4
2
4
2
≤ 6 → result[2] = 6 - 2 =
4
prices
8
0
4
1
6
2
2
3
3
4
i
result
4
2
4
item
2
: find the first price to its right that is
≤ it
prices
8
0
4
1
6
2
2
3
3
4
j
i
result
4
2
4
2
nothing cheaper to the right → keep price
2
prices
8
0
4
1
6
2
2
3
3
4
i
result
4
2
4
2
item
3
: find the first price to its right that is
≤ it
prices
8
0
4
1
6
2
2
3
3
4
result
4
2
4
2
3
return
[4, 2, 4, 2, 3]
algo
master
.
io
Step:
Brute force: for each item, scan right for the first price <= it.
0 / 14
Input
Input 1
Input 2
Input 3
Custom
prices
=
[8, 4, 6, 2, 3]
0 / 14
algo
master
.
io
Step:
Brute force: for each item, scan right for the first price <= it.
