Stack Problems

Stacks are particularly useful for problems involving matching, nesting, or processing elements in reverse order.

Decode String

Problem Link

Given an encoded string like "3[a]2[bc]", return its decoded string "aaabcbc".

The encoding rule is: k[encoded_string], where the encoded string inside brackets is repeated exactly k times.

Example

  • Input: s = “3[a]2[bc]”
  • Output: “aaabcbc”

Solution

def stacky(s):
    """
    When we hit an open bracket, we know we have parsed k for the contents of the bracket, 
    so push (current_string, k) to the stack, so we can pop them on closing bracket 
    to duplicate the enclosed string k times.
    """
    stack = []
    current_string = ""
    k = 0

    for char in s:
        if char == "[":
            # Just finished parsing this k, save current_string and k for 
            # when we pop
            stack.append((current_string, k))
            # Reset current_string and k for this new frame
            current_string = ""
            k = 0
        elif char == "]":
            # We have completed this frame, get the last current_string and k           
            # from when the frame opened, which is the k we need to duplicate 
            # the current current_string by
            last_string, last_k = stack.pop(-1)
            current_string = last_string + last_k * current_string
        elif char.isdigit():
            k = k * 10 + int(char)
        else:
            current_string += char

    return current_string

Generate Parentheses

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Example

  • Input: n = 3
  • Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

Brute Force Approach

def valid(self, s: str):
    open = 0
    for c in s:
        open = (open+1) if c=="(" else (open-1)
        if open < 0:
            # We have a closing parantheses that we cannot match..
            return False
    return (open == 0)

def generateParenthesis(self, n: int) -> List[str]: 
    res = []
    def dfs(s):
        if len(s) == 2*n:
            if valid(s): # We dont want ELSE to run if valid(s) is false.
                res.append(s)
        else:
            dfs(s + "(")
            dfs(s + ")")

    dfs("")
    return res

Optimized Backtracking Approach

def generateParenthesis(self, n: int) -> List[str]:
    stack = []
    res = []

    def dfs(openN, closedN):
        if openN == closedN == n:
            res.append("".join(stack))
        else:
            if openN < n:
                stack.append("(")
                dfs(openN+1, closedN)
                stack.pop()
            if closedN < openN <= n:
                stack.append(")")
                dfs(openN, closedN+1)
                stack.pop()
    
    dfs(0, 0)
    return res

Monotonic Stacks

Monotonic Stacks are used when you need to traverse an array with a fixed pointer, but also need to efficiently backtrack to smaller/larger elements than the current element without moving your pointer.

Next Greater Element

Given nums, find the next greater element for each element in the array. If an element does not have a next greater element, use -1.

def nextGreaterElement(nums):
  n = len(nums)
  result = [-1] * n
  stack = []

  for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
      idx = stack.pop()
      result[idx] = nums[i]
    stack.append(i)

  return result

Daily Temperatures

Return an array where each element is the number of days you need to wait for a warmer temperature.

def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
    stack = [] # holds indexes, not values
    res = [0] * len(temperatures)

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            res[stack[-1]] = (i - stack[-1]) # distance
            stack.pop()
        stack.append(i)
    return res