Medium

Intuition Most of the cases, if the question asks for O(1), there’s probably a set or hashmap involced. This question uses the set to check if the next number is in the set (making a sequence) Approach The key is that the set provides a near O(1) access, making the solution O(n) Complexity Time complexity: Space complexity: Code class Solution(object): def longestConsecutive(self, nums): """ :type nums: List[int] :rtype: int """ longest = 0 num_set = set(nums) for num in num_set: if num-1 not in num_set: current = num curr_streak = 1 while current + 1 in num_set: current += 1 curr_streak += 1 longest = max(curr_streak, longest) return longest

Intuition The linked list is naturally in the reverse order we need to do the math. Keep a carry flag, special edge case at the final loop. Approach Traverse the linked list until there are no next elements in both lists. Sum both numbers, if carry is true, add 1 and set carry to false if > 9, set carry to true after the final iteration, if carry is true, add the last node with val = 1 ...

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)