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;
}