Math

Intuition Keep a hash map of numbers and it’s indexes: hashmap[num] = index Approach Calculate the complement (target - num[i]). if complements exists in hashmap, return indexes if not, add the current number the the hashmap hashmap[num] = index. Complexity Time complexity: O(n) Space complexity: O(n) Code class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ m = len(nums) r = range(m) compl = {} for i in r: complement = target - nums[i] if complement in compl: return [i, compl[complement]] compl[nums[i]] = i return []

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 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 Brute force, but it doesn’t work. Approach I had to read the solution. The key is math, the order of a product operation do not affect the final result. Visualization makes it easier. A*B*C*D = (A*B)*(C*D) Let’s see one example in action. Consider the following array n=[2,2,3,2,2] When calculating the answer for n[2], we are calculating the product of two separated grous (2*2) * (2*2), left L and right R independently. ...