Introduction

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.

Problem 1: Preceding Smaller Elements

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.

Problem 1: Naive Approach

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!

Problem 1: Efficient Approach with Stacks

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 lets you access the most recent relevant information efficiently.

Sign up
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal