Hello World

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 Use recursion to traverse the tree, always returning the max value of the right and left tree. Approach Complexity Time complexity: O(n) Space complexity: O(log(n)), in case the tree is balanced Code # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def maxDepth(self, root): """ :type root: Optional[TreeNode] :rtype: int """ return self.maxD(root, 0) def maxD(self, root, level): if not root: return level return max(self.maxD(root.left, level+1),self.maxD(root.right, level+1))

Intuition Check all items simultaneosly Approach Complexity Time complexity: O(n) Space complexity: O(1) Code # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def isSameTree(self, p, q): """ :type p: Optional[TreeNode] :type q: Optional[TreeNode] :rtype: bool """ if not p and not q: return True if not p or not q: return False if p.val != q.val: return False return self.isSameTree(p.right, q.right) and self.isSameTree(p.left, q.left)

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 ...