Easy

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 Map characters letters, and map seen letters. Approach We will need to use two use two structures here. One to map the correspoding character One to keep track of seen chracters, this is necessary becase “no two chracter may map to the same character” If len is diff, just return false. Loop through the chracters (s -> cs, t -> ct). if cs was mapped before, and map[cs] == ct, move to the next if cs was mapped before, and map[cs] != ct, return False if cs was not mapped before, and seen[ct], return False else map[cs] = ct, and seen[ct] = True Complexity Time complexity: O(n) ...

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

Intuition Count frequency of each Approach Create a map conting the frequency of one string. For the second string decrease by one each letter: If the count of a given letter is < 0, returns false If the letter does not yet exists in the map, returns false Complexity Time complexity: O(n) Space complexity: O(n) Code class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ if len(s) != len(t): return False letters = {} for c in s: if c in letters: letters[c] += 1 else: letters[c] = 1 for c in t: if c in letters: letters[c] -= 1 if letters[c] < 0: return False else: return False return sum(letters.values()) == 0 But there’s a even shorter version: ...