Hashmap

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 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 Create a map os strings, group by it’s sorted version. Approach Create a map os strings, group by it’s sorted version. Complexity Time complexity: O(n logn) Space complexity: O(n) Code class Solution(object): def groupAnagrams(self, strs): """ :type strs: List[str] :rtype: List[List[str]] """ _map = {} for s in strs: _sorted = "".join(sorted(s)) if _sorted in _map: _map[_sorted].append(s) else: _map[_sorted] = [s] return _map.values()