Stack Practice

Adding stacks to my toolbelt

A stack has never been a data structure I've reached for. All these Leetcode problems under the Stacks section never really made me think of using a stack either. I would only have been able to do the brute force solution in the past, but I'm starting to see how the stack is helpful here.

The major breakthrough came when I realized you could put a Tuple or an Object on the stack, not just a string or a number. In hindsight, this seems pretty obvious, but I never thought of it before. I'm still in the "easy" questions for now while I get more familiar with the idea and how to implement it, but I hope to move up to mediums soon. Probably stick that in a new post though and maybe I'll have another interesting breakthrough to write about too.

Leetcode #1475 - Final Prices With a Special Discount in a Shop

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.

function Stack() {
    const stack = Object.create(new Array());
 
    stack.top = () => {
        return stack.length < 1 ? undefined : stack[stack.length - 1];
    }
 
    return stack;
}
 
function finalPrices(prices: number[]): number[] {
    const stack = Stack();
    const discounts = [];
 
    for (let index = 0; index < prices.length; index += 1) {
        const price = prices[index];
 
        if (stack.length < 1) {
            stack.push([price, index]);
        } else {
            while (stack.top() !== undefined && stack.top()[0] >= price) {
                const [oldPrice, oldIndex] = stack.pop();
 
                discounts[oldIndex] = oldPrice - price;
            }
 
            stack.push([price, index]);
        }
    }
 
    while(stack.top() !== undefined) {
        const [price, index] = stack.pop();
 
        discounts[index] = price;
    }
 
    return discounts;
};