Welcome back! As we move forward with our TypeScript algorithmic journey, today we will continue working with stacks. During your coding interviews, it’s common to encounter puzzles that these structures can solve gracefully and efficiently. By diving into two stack-centric problems today, you'll see firsthand just how invaluable a well-implemented stack can be for writing clean and efficient code.

Consider a sequence of integers like the peaks and valleys of a mountain range. Each peak has a height represented by a number, and you're hiking from left to right, recording peaks shorter than the one you're currently on. For each peak, we want to find out the height of the nearest preceding peak that's lower than it — a classic problem where stacks excel.

Envision analyzing daily temperatures over several months. You're interested in knowing the last cooler day for each day you examine. This mirrors our array problem, where we're seeking the previous smaller number before each entry in the array. It’s these kinds of performance-sensitive tasks that stack operations handle without breaking a sweat.

You might be tempted to approach this problem with the vigor of a brute force assault — looking behind each element to find a smaller one. However, this could mean reviewing multiple times and spending unforgiving time as you consider each element repeatedly. In a vast data set, this would be akin to retracing your steps on each day's hike to find a shorter peak, an exhausting proposition!

With stacks, we take on the role of a photographer capturing a time-lapse of a hiking journey. Imagine each time you reach a peak, you take a photo that captures the current peak and any shorter peaks bolstering it from the past. This way, when reviewing the photos, you can quickly identify the last peak that was shorter without having to recall every detail of the ascent. Just like glancing through your last snapshot, the stack lets you access the most recent relevant information efficiently.

Let's lace up our boots and start the ascent by iterating through the array of peak heights and interacting with our stack.

TypeScript
Copy to clipboard
1function findPrecedingSmallerElements(arr: number[]): number[] {
2    let stack: number[] = [];
3    let result: number[] = new Array(arr.length).fill(-1);
4
5    for (let i = 0; i < arr.length; i++) {
6        while (stack.length > 0 && stack[stack.length - 1] >= arr[i]) {
7            stack.pop();
8        }
9        if (stack.length > 0) {
10            result[i] = stack[stack.length - 1];
11        }
12        stack.push(arr[i]);
13    }
14    return result;
15}
16
17console.log(findPrecedingSmallerElements([1, 3, 2, 5, 4, 7]));
18// Output: [ -1, 1, 1, 2, 2, 4 ]
19console.log(findPrecedingSmallerElements([5, 4, 3, 2, 1]));
20// Output: [ -1, -1, -1, -1, -1 ]

In our code, we trek through each element in the array. Our conditions within the loop perform the 'pop' work — discarding any peak that isn't lower than our current one, ensuring that only useful candidates remain. Then, we notate the result — either -1 if no such peak exists or the last peak remaining on the stack. Before moving on, we add our current peak to the stack.

Our second challenge is a high-stakes game where you must keep track of your score and always be aware of your lowest score without slowing down the game. Enter the MinStack, a special stack designed to efficiently keep track of the minimal score.

A naive solution would involve, at the end of each turn, traversing through all the scores recorded to that point to find the minimum score — similar to going through every high score ever recorded for each new score. Time-wise, this would mean when 100 scores are recorded, up to 100 checks would be needed each turn, leading to $O(n^2)$ operations as the game progresses.

We envision a second stack, which shadows our main stack. As the main stack grows, this auxiliary stack captures and retains only the minimal elements seen up to each point. Thus, the minimum score is always at the top of our 'min stack'.

It's time to manifest this brainchild into TypeScript code. Here's the skeletal structure of our MinStack, waiting to be imbued with functionality:

TypeScript
Copy to clipboard
1class MinStack {
2    private stack: number[];
3    private minStack: number[];
4
5    constructor() {
6        this.stack = []; // main stack
7        this.minStack = []; // track minimum
8    }
9
10    push(val: number): void {
11        this.stack.push(val); // add value to stack
12        if (this.minStack.length === 0 || val <= this.getMin()) {
13            this.minStack.push(val); // update minimum
14        }
15    }
16
17    pop(): number | undefined {
18        const item = this.stack.pop(); // remove top value
19        if (item === this.getMin()) {
20            this.minStack.pop(); // remove top minimum
21        }
22        return item;
23    }
24
25    top(): number | undefined {
26         // return top value
27        return this.stack[this.stack.length - 1];
28    }
29
30    getMin(): number | undefined {
31        // return minimum value
32        return this.minStack[this.minStack.length - 1]; 
33    }
34}

The push method introduces the key player — our minStack, which retains the minimum value observed every time we add a new entry. Meanwhile, the pop operation is like a relay race transition, handing off the title "minimum" to the next contender when the current titleholder is knocked off the podium.

Simulating the pushing of various elements onto the stack and invoking getMin would yield the correct minimum every time, thanks to our additional stack, minStack.

TypeScript
Copy to clipboard
1let ms = new MinStack();
2ms.push(5);
3console.log(ms.getMin());  // 5
4ms.push(7);
5console.log(ms.getMin());  // 5
6ms.push(3);
7console.log(ms.getMin());  // 3
8ms.push(1);
9console.log(ms.getMin());  // 1

Our expedition through stack-land today has shown us that stacks can be the clever trick up your sleeve for certain types of interview questions. We have seen how to keep track of past element states with "Preceding Smaller Elements" and maintain instant access to the minimum element in our MinStack. From trails to inventory — stacks reveal their flexibility and efficiency. Thus, your toolbox of algorithms has just received a shiny new set of tools, bolstering your confidence for what lies ahead — practice!