Stack

Intuition Compute values on the fly, use stack for brackets. Approach Parse each number, use num = 10xnum + current. Keep track of the last sign (starts as positive). When an opening bracket is found, stack the item and the sign. When a closing bracket is found, pop sign and item and do the math. Complexity Time complexity: O(N) Space complexity: O(N) Code class Solution(object): def calculate(self, s): """ :type s: str :rtype: int """ stack = [] res = 0 num = 0 sign = 1 for c in s: if c.isdigit(): num = (num * 10 ) + int(c) elif c == "+": res += sign * num sign = 1 num = 0 elif c == "-": res += sign * num sign = -1 num = 0 elif c == "(": stack.append(res) stack.append(sign) sign = 1 res = 0 elif c == ")": res += sign * num res *= stack.pop() # sign res += stack.pop() # num num = 0 return res + sign * num

Intuition Use a stack to pile all numbers, when an operator is found, pop the last two numbers, do the calculation and then push it to the stack again. Assuming the expression is valid, at the end thre will be only one element in the stack that is the result. Approach Complexity Time complexity: O(n) Space complexity: O(n) Code class Solution(object): def evalRPN(self, tokens): """ :type tokens: List[str] :rtype: int """ stack = [] for t in tokens: if self.is_op(t): right = stack.pop() left = stack.pop() if t == "/": stack.append(self.div(left , right)) elif t == "*": stack.append(left * right) elif t == "+": stack.append(left + right) elif t == "-": stack.append(left - right) else: stack.append(int(t)) return stack[0] def div(self, left, right): r = left / right if r < 0 and right * r != left: return r + 1 return r def is_op(self, token): return token == "/" or token == "*" or token == "+" or token == "-"

Intuition Use a stack to keep current element and current_min Approach Use a stack to keep current element and current_min Complexity Time complexity: O(1) Space complexity: O(n) Code class MinStack(object): def __init__(self): self.stack = [] self.min = float('inf') def push(self, val): """ :type val: int :rtype: None """ self.min = min(val, self.min) item = { "val": val, "min": self.min } self.stack.append(item) def pop(self): """ :rtype: None """ self.stack.pop() if len(self.stack) > 0: self.min = self.stack[-1]['min'] else: self.min = float('inf') def top(self): """ :rtype: int """ return self.stack[-1]["val"] def getMin(self): """ :rtype: int """ return self.min

Intuition Split path by /, use a stack to push or pop elements. Approach Split the absolute path by ‘/’. For each element If it’s empty, skip If it’s ., skip If it’s .. and the stack has element, pop Else push to the stack Concat everything and return Complexity Time complexity: O(n) Space complexity: O(n) Code class Solution(object): def simplifyPath(self, path): """ :type path: str :rtype: str """ dirs = [] for d in split(path, "/"): if len(d) == 0: continue if d == ".": continue if d == "..": if len(dirs) > 0: dirs.pop() else: dirs.append(d) return "/" + "/".join(dirs)

Intuition Recursive approach won’t work, it’s too expensive. Approach Use a stack to keep track of the opening brackets. Whenever we see a closing bracket, we check if the top of the stack has the corresponding closing one. When we see a closing bracket we will return False if the stack: Does not have any element The top of the stack does not match with the closing bracker After going through all character, if there’s any element left in the stack, we also return False. ...