Intro

This will be a very short article, as the Blind 75 list only contains 1 problem revolving around the stack data structure. It is still a good pattern to learn, as there are several stack problems you may encounter, but they all follow the same pattern.

Stacks are like limited arrays. Stacks are also LIFO (Last-In-First-Out Ordering), such that the last element you push on to it, is the first one that will be removed. You can think of them like Stacks of plates. Stacks feature several functions for the user to interact with, such as: Pop Peek and Push.

• Push as you would expect pushes a new value on to the stack. Adding at the end on an array is O(1); it always takes the same amount of time, regardless of the size of the array.
• Peek allows you to view the top most object in the stack, without removing it from the stack entirely.
• Pop removes the top-most value from the stack, and it is gone forever from the stack.

The term "Stack Overflow" is based on the Stack data structure. When your CPU continually pushes return addresses onto a stack, but those addresses are never removed, your CPU Stack memory 'overflows' and crashes your application. This can happen in infinite loops when the return address of your function is never removed from memory.

Valid Parentheses

Here is a very well-known Stack problem. It is a leetcode easy so let's briefly run through it together.

Brute Force

Since we know this is a stack problem, let's derive a brute force solution. First off, we need to know whether to push or pop characters on the stack. If know if the character is a closing bracket, we will not be pushing on to the stack. The quickest way to check this in constant time is a HashTable given the consistent lookup they give us.

So to start, we need a dictionary to search the beginning and ending brackets. Something resembling [")":"(" , "]": "[" , "}": "{"].

Now we go character by character. If the character is a key in our dictionary, and the value equals that key, we can pop off the stack. If by the end of our traversal we have a non-empty stack we know the string is not valid.

for letter in string
    if top of stack equals the inverse bracket of our letter, pop from the stack 
    else push on the stack
    
return if stack is empty

Time complexity here at worst is O(n), because we need to traverse every letter in the string. Peeking pushing and popping from a stack is O(1) time. Space complexity here is O(1) due to the fixed nature of our hashTable. It does not grow.

This solution is great and all but there are certain scenarios in which we are doing extra work. Think of the example "()]()", if in the middle of our iteration we encounter a non-balanced character, we know we can return false early. Let's dive deeper into this.

[ Enhanced Stack ]

[ O(n) average time + O(1) space ]

We need to think when we would find a time to return from the function early.

First off, we know we should push onto the stack, if we encounter an opening brace. We can explicitly check for that.

Second off, if we encounter a closing bracket (another explicit check), we should check if the stack is empty. If the stack is empty, we can bail early because there is not an associated opening bracket for our close bracket.

Pseudocode:

for letter in string
    if opening bracket
        push on stack
    if closing bracket
        if stack empty
            return false
        else 
            if the top of the stack is the inverse of our closing bracket
                pop from stack
            else 
                return false

return stack is empty or not

This keeps the same time complexity & space complexity from earlier, but it just saves us some work in specific input cases. Here is the final solution:

var stack = [Character]()
var hash: [Character:Character] = [")":"(", "}":"{","]":"["]

for letter in s {
    if letter == "(" || letter == "{" || letter == "[" {
        stack.append(letter)
    } else if letter == ")" || letter == "}" || letter == "]" {
        guard stack.count != 0, stack.last! == hash[letter] else { return false }
        stack.popLast()
    }
}
return stack.count == 0

Cheers! On to the next section.