Mastering Stack-Based Problem Solving in Kotlin

Introduction to the Lesson

In this session, we will delve into the world of coding interviews by focusing on stack-based problems . We will endeavor to decode interview questions that leverage the Last-In, First-Out (LIFO) behavior 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 a deep understanding of data structures.

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 an integer, 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.

Problem 1: Actualization

Envision analyzing daily temperatures over several months. You're interested in knowing the most recent 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 time-sensitive queries that stack operations handle effortlessly.

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

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.

Join the 1M+ learners on CodeSignal

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

Problem 2: Solution Building

It's time to manifest this brainchild into Kotlin code. Here's the skeletal structure of our MinStack:

Kotlin

import java.util.ArrayDeque

class MinStack {
    private val stack = ArrayDeque<Int>()
    private val minValues = ArrayDeque<Int>()
    
    fun push(x: Int) {
        if (minValues.isEmpty() || x <= minValues.last()) {
            minValues.addLast(x)
        }
        stack.addLast(x)
    }
    
    fun pop() {
        if (stack.isNotEmpty() && stack.last() == minValues.last()) {
            minValues.removeLast()
        }
        if (stack.isNotEmpty()) {
            stack.removeLast()
        }
    }
    
    fun top(): Int {
        return if (stack.isEmpty()) -1 else stack.last()
    }
    
    fun getMin(): Int {
        return if (minValues.isEmpty()) -1 else minValues.last()
    }
}

import java.util.ArrayDeque

class MinStack {
    private val stack = ArrayDeque<Int>()
    private val minValues = ArrayDeque<Int>()
    
    fun push(x: Int) {
        if (minValues.isEmpty() || x <= minValues.last()) {
            minValues.addLast(x)
        }
        stack.addLast(x)
    }
    
    fun pop() {
        if (stack.isNotEmpty() && stack.last() == minValues.last()) {
            minValues.removeLast()
        }
        if (stack.isNotEmpty()) {
            stack.removeLast()
        }
    }
    
    fun top(): Int {
        return if (stack.isEmpty()) -1 else stack.last()
    }
    
    fun getMin(): Int {
        return if (minValues.isEmpty()) -1 else minValues.last()
    }
}

The push method introduces the key player — our minValues list, 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 would yield the correct minimum every time, thanks to our additional minValues list.

Introduction to the Lesson

Problem 1: Preceding Smaller Elements

Problem 1: Actualization

Problem 1: Naive Approach

Problem 1: Efficient Approach

Join the 1M+ learners on CodeSignal

Problem 1: Solution Building

Problem 1: Efficiency Analysis

Problem 2: Stack with Minimum Trace

Problem 2: Naive Approach

Problem 2: Efficient Approach

Problem 2: Solution Building

Problem 2: Efficiency Analysis

Lesson Summary