Stacks in Coding Interviews: Advanced Techniques and Implementations in C#

Introduction to the Lesson

Hello once again, champion of code! In this session, we will delve into the world of coding interviews by focusing on stack-based problems. We endeavor to decode interview questions that leverage the Last-In, First-Out (LIFO) magic of stacks to offer elegantly efficient solutions. After today, not only will you be able to handle stacks with ease, but you'll also be able to articulate and apply this knowledge when faced with interview questions that require depth in data structure understanding.

Problem 1: Preceding Smaller Elements

Imagine a sequence of integers representing the highs and lows of a mountain range. Each integer denotes the height of a peak, and you're moving from left to right, tracking peaks that are shorter than the current one you're standing on. For every peak, the task is to identify the height of the nearest preceding peak that is shorter — a scenario perfectly suited for stacks. Alternatively, think about monitoring daily temperatures over several months. You're interested in determining the last day when the temperature was cooler for each day you check. This is analogous to finding the previous smaller number for each entry in the array. Stacks excel at handling these types of sequence queries efficiently.

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 excessive 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

Enter the stack — our trusty guide. As we progress through the array, we push peaks onto the stack. When we encounter a peak (arr[i]), we pop entries from the stack that aren't shorter than the current one. The stack's top now reveals the nearest preceding smaller peak, which we note before adding the current peak to the stack.

Problem 1: Solution Building

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

using System; using System.Collections.Generic; public class PrecedingSmallerElements { public static int[] FindPrecedingSmallerElements(int[] arr) { int[] result = new int[arr.Length]; Stack<int> stack = new Stack<int>(); for (int i = 0; i < arr.Length; i++) { while (stack.Count != 0 && stack.Peek() >= arr[i]) { stack.Pop(); } result[i] = stack.Count == 0 ? -1 : stack.Peek(); stack.Push(arr[i]); } return result; } public static void Main(string[] args) { int[] arr = { 3, 7, 1, 5, 4, 3 }; int[] result = FindPrecedingSmallerElements(arr); Console.WriteLine(string.Join(" ", result)); // Output: -1 3 -1 1 1 1 } }

Problem 2: Solution Building

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

using System;
using System.Collections.Generic;

public class MinStack
{
    private Stack<int> stack = new Stack<int>();
    private Stack<int> minValues = new Stack<int>();

    // The push method is where most of our logic resides.
    public void Push(int x)
    {
        if (minValues.Count == 0 || x <= minValues.Peek())
        {
            minValues.Push(x);
        }
        stack.Push(x);
    }

    // Each pop requires careful coordination between our two stacks.
    public void Pop()
    {
        if (stack.Count != 0 && stack.Peek() == minValues.Peek())
        {
            minValues.Pop();
        }
        if (stack.Count != 0)
        {
            stack.Pop();
        }
    }

    // The Top method reveals the peak of our stack cable car.
    public int Top()
    {
        return stack.Count == 0 ? -1 : stack.Peek();
    }

    // GetMin serves as our on-demand minimum value provider.
    public int GetMin()
    {
        return minValues.Count == 0 ? -1 : minValues.Peek();
    }
}

class Program
{
    public static void Main(string[] args)
    {
        MinStack minStack = new MinStack();
        minStack.Push(5);
        minStack.Push(3);
        Console.WriteLine(minStack.GetMin()); // Output: 3
        minStack.Pop();
        Console.WriteLine(minStack.GetMin()); // Output: 5
    }
}

using System;
using System.Collections.Generic;

public class MinStack
{
    private Stack<int> stack = new Stack<int>();
    private Stack<int> minValues = new Stack<int>();

    // The push method is where most of our logic resides.
    public void Push(int x)
    {
        if (minValues.Count == 0 || x <= minValues.Peek())
        {
            minValues.Push(x);
        }
        stack.Push(x);
    }

    // Each pop requires careful coordination between our two stacks.
    public void Pop()
    {
        if (stack.Count != 0 && stack.Peek() == minValues.Peek())
        {
            minValues.Pop();
        }
        if (stack.Count != 0)
        {
            stack.Pop();
        }
    }

    // The Top method reveals the peak of our stack cable car.
    public int Top()
    {
        return stack.Count == 0 ? -1 : stack.Peek();
    }

    // GetMin serves as our on-demand minimum value provider.
    public int GetMin()
    {
        return minValues.Count == 0 ? -1 : minValues.Peek();
    }
}

class Program
{
    public static void Main(string[] args)
    {
        MinStack minStack = new MinStack();
        minStack.Push(5);
        minStack.Push(3);
        Console.WriteLine(minStack.GetMin()); // Output: 3
        minStack.Pop();
        Console.WriteLine(minStack.GetMin()); // Output: 5
    }
}

The Push method introduces the key player — our minValues stack, which retains the minimum value observed so far 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 yields the correct minimum every time, thanks to our additional stack, minValues.

Introduction to the Lesson

Problem 1: Preceding Smaller Elements

Problem 1: Naive Approach

Problem 1: Efficient Approach

Problem 1: Solution Building

Join the 1M+ learners on CodeSignal

Problem 2: Stack with Minimum Trace

Problem 2: Naive Approach

Problem 2: Efficient Approach

Problem 2: Solution Building

Lesson Summary