Efficient Stack Management and Implementation in Go

Introduction to the Lesson

Hello once again, champion of code! In this session, we will delve into stack-based problems. We endeavor to decode 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 problems that require depth in data structure understanding.

Problem 1: First Preceding Smaller Elements

Imagine monitoring the daily stock prices of a company over a period. Each price represents the stock's value at the end of a trading day. For every trading day, the task is to identify the first previous day when the stock price was lower. This scenario is perfectly suited for stacks, allowing us to efficiently track the nearest preceding smaller value in the sequence. Stacks enable quick and efficient resolution of such linear sequence queries by leveraging the Last-In, First-Out (LIFO) property. Alternatively, think about monitoring daily temperatures over several months. You're interested in determining the first previous 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 a brute-force method — checking behind each stock price to find a lower one. However, this approach means iterating through each price for every day, which can become inefficient when dealing with a large dataset. In financial terms, it's like reviewing every past day's stock price each day to find a lower one — an arduous undertaking!

Problem 1: Efficient Approach

Enter the stack — our reliable ally. In Go, stacks are typically managed using slices. As we progress through the array, we simulate stack behavior by appending elements and removing them using slice operations. When we examine a stock price, we remove entries from our slice that aren't lower than the current price. The top of the slice represents the nearest preceding day with a lower stock price.

Join the 1M+ learners on CodeSignal

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

func FindFirstPrecedingSmallerElements(arr []int) []int {
    result := make([]int, len(arr))
    stack := []int{}

    for i := 0; i < len(arr); i++ {
        for len(stack) != 0 && stack[len(stack)-1] >= arr[i] {
            stack = stack[:len(stack)-1] // Pop from stack
        }
        if len(stack) == 0 {
            result[i] = -1
        } else {
            result[i] = stack[len(stack)-1]
        }
        stack = append(stack, arr[i]) // Push to stack
    }

    return result
}

func FindFirstPrecedingSmallerElements(arr []int) []int {
    result := make([]int, len(arr))
    stack := []int{}

    for i := 0; i < len(arr); i++ {
        for len(stack) != 0 && stack[len(stack)-1] >= arr[i] {
            stack = stack[:len(stack)-1] // Pop from stack
        }
        if len(stack) == 0 {
            result[i] = -1
        } else {
            result[i] = stack[len(stack)-1]
        }
        stack = append(stack, arr[i]) // Push to stack
    }

    return result
}

package main

import "fmt"

type MinStack struct {
    stack    []int
    minStack []int
}

func (s *MinStack) Push(x int) {
    if len(s.minStack) == 0 || x <= s.minStack[len(s.minStack)-1] {
        s.minStack = append(s.minStack, x)
    }
    s.stack = append(s.stack, x)
}

func (s *MinStack) Pop() {
    if len(s.stack) > 0 {
        if s.stack[len(s.stack)-1] == s.minStack[len(s.minStack)-1] {
            s.minStack = s.minStack[:len(s.minStack)-1]
        }
        s.stack = s.stack[:len(s.stack)-1]
    }
}

func (s *MinStack) Top() int {
    if len(s.stack) == 0 {
        return -1
    }
    return s.stack[len(s.stack)-1]
}

func (s *MinStack) GetMin() int {
    if len(s.minStack) == 0 {
        return -1
    }
    return s.minStack[len(s.minStack)-1]
}

func main() {
    minStack := MinStack{}
    minStack.Push(5)
    minStack.Push(3)
    fmt.Println(minStack.GetMin()) // Output: 3
    minStack.Pop()
    fmt.Println(minStack.GetMin()) // Output: 5
}

package main

import "fmt"

type MinStack struct {
    stack    []int
    minStack []int
}

func (s *MinStack) Push(x int) {
    if len(s.minStack) == 0 || x <= s.minStack[len(s.minStack)-1] {
        s.minStack = append(s.minStack, x)
    }
    s.stack = append(s.stack, x)
}

func (s *MinStack) Pop() {
    if len(s.stack) > 0 {
        if s.stack[len(s.stack)-1] == s.minStack[len(s.minStack)-1] {
            s.minStack = s.minStack[:len(s.minStack)-1]
        }
        s.stack = s.stack[:len(s.stack)-1]
    }
}

func (s *MinStack) Top() int {
    if len(s.stack) == 0 {
        return -1
    }
    return s.stack[len(s.stack)-1]
}

func (s *MinStack) GetMin() int {
    if len(s.minStack) == 0 {
        return -1
    }
    return s.minStack[len(s.minStack)-1]
}

func main() {
    minStack := MinStack{}
    minStack.Push(5)
    minStack.Push(3)
    fmt.Println(minStack.GetMin()) // Output: 3
    minStack.Pop()
    fmt.Println(minStack.GetMin()) // Output: 5
}

func FindFirstPrecedingSmallerElements(arr []int) []int {
    result := make([]int, len(arr))
    stack := []int{}

    for i := 0; i < len(arr); i++ {
        for len(stack) != 0 && stack[len(stack)-1] >= arr[i] {
            stack = stack[:len(stack)-1] // Pop from stack
        }
        if len(stack) == 0 {
            result[i] = -1
        } else {
            result[i] = stack[len(stack)-1]
        }
        stack = append(stack, arr[i]) // Push to stack
    }

    return result
}

package main

import "fmt"

type MinStack struct {
    stack    []int
    minStack []int
}

func (s *MinStack) Push(x int) {
    if len(s.minStack) == 0 || x <= s.minStack[len(s.minStack)-1] {
        s.minStack = append(s.minStack, x)
    }
    s.stack = append(s.stack, x)
}

func (s *MinStack) Pop() {
    if len(s.stack) > 0 {
        if s.stack[len(s.stack)-1] == s.minStack[len(s.minStack)-1] {
            s.minStack = s.minStack[:len(s.minStack)-1]
        }
        s.stack = s.stack[:len(s.stack)-1]
    }
}

func (s *MinStack) Top() int {
    if len(s.stack) == 0 {
        return -1
    }
    return s.stack[len(s.stack)-1]
}

func (s *MinStack) GetMin() int {
    if len(s.minStack) == 0 {
        return -1
    }
    return s.minStack[len(s.minStack)-1]
}

func main() {
    minStack := MinStack{}
    minStack.Push(5)
    minStack.Push(3)
    fmt.Println(minStack.GetMin()) // Output: 3
    minStack.Pop()
    fmt.Println(minStack.GetMin()) // Output: 5
}

Introduction to the Lesson

Problem 1: First Preceding Smaller Elements

Problem 1: Naive Approach

Problem 1: Efficient Approach

Join the 1M+ learners on CodeSignal

Problem 1: Solution Building

Problem 2: Stack with Minimum Trace

Problem 2: Naive Approach

Problem 2: Efficient Approach

Problem 2: Solution Building

Lesson Summary