Patterns

Arrays & Hashing
Sliding Window & 2 pointers
Tree
Subset level by level (BFS/DFS)
Modified Binary Search (O(log(n))) / O(log(m * n))
Top K elements (Heap)
Linked List
DP

Sliding Window and Two Pointers

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Input: s = "zxyzxyz" #Output: 3
        # Approach Sliding Window
        char_set = set()
        l = 0
        res = 0
        for r in range(len(s)):
            while s[r] in char_set:
                char_set.remove(s[l])
                l += 1
            char_set.add(s[r])
            res = max(res, r - l + 1)
        return res

Tree

Recursive Solutions and DFS/BFS are often used
queue is used to implement BFS. In python its deque() which has append() ,popleft() and pop() (pop right) function

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        # Swap the children
        tmp = root.left
        root.left = root.right
        root.right = tmp
        
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        #O(n) Time complexity
        self.res = 0
        def dfs(curr):
            if not curr:
                return 0
            
            left = dfs(curr.left)
            right = dfs(curr.right)
            
            self.res = max(self.res, left + right)
            return 1 + max(left, right)
        
        dfs(root)
        return self.res

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []
        q = deque()
        if root:
            q.append(root)

        while q:
            val = []

            for i in range(len(q)):
                node = q.popleft()
                val.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(val)
        return res

Modified Binary Search

Usually be aware of pivot = low + 1 to check do you really need to move the pivot + 1 or - 1.

Subset

To figure out if it is a subset question, plot a decision tree

Questions will be related to combination subset, permutation subset etc.

Usually Recursive Solutions (Backtracking) with BFS or DFS or slack. In implementation usually a list is used.
Usually O(n2^n)

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        subset = []
        # [1, 2, 3]
        def dfs(i):
            if i >= len(nums):
                res.append(subset.copy())
                return
            
            # decision to include nums[i]
            subset.append(nums[i])
            dfs(i + 1)

            # decision to include nums[i]
            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res
            
# Input: nums=[1,2,3]
# Output: [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]

Make sure to use .copy() when appending in such questions.

LinkedList

# Definition for singly-linked list.
class Node:
    def __init__(self, val=0, next=None):
        self.val = val
         self.next = next

LinkedList insert and remove are O(1) because it is done in the last node (or first node in Double Linked List).

Floyd’s Tortoise and Hare Algorithm

Two pointers in Linked List

LRU (Least Recent Used cache)

A popular question using LinkedList.

Double Linked List <—>
Leftmost Least Recent <------> Most Recent Rightmost

# Create a customized Node implementation
class Node:
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {} # Map key to nodes

        # Least Recent <------> Most Recent
        self.left, self.right = Node(0, 0), Node(0, 0)
        # Connect them together
        self.left.next = self.right
        self.right.prev = self.left

    def remove(self, node):
        # Support func to remove node from linked list
        prev_node, next_node = node.prev, node.next
        prev_node.next, next_node.prev = next_node, prev_node
    
    def insert(self, node):
        # Support func to insert node at the rightmost
        prev_node, next_node = self.right.prev, self.right
        prev_node.next, next_node.prev = node, node
        node.prev, node.next = prev_node, next_node

    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1
        

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])

        if len(self.cache) > self.cap:
            # remove LRU from the hashmap and the list
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]

DP

Bottom Up approach (storing base cases values)

Usage

Try to use range all the time, less confusion

prices = [1,2,3,4]
for i in range(0, len(prices)):
  print(prices[i]) # [1,2,3,4]
for i in range(0, len(prices), -1):
  print(prices[i]) # [4,3,2,1]

Playing with strings

Sort and Reverse string

You cannot sort a string or reverse a string using default functions (e.g. reversed(), .sort()).
You can use s[::-1] to reverse the string.

Checking a char is not special character, we can use this .isalnum() (built-in function). Otherwise you can leverage ascii code ord() and char().

def isPalindrome(self, s: str) -> bool:
    new_str = ""
    for c in s:
        if c.isalnum():
            new_str += c.lower()
    return new_str == new_str[::-1]

Sets

Sets cannot contain duplicate. Therefore we can simply check the length of list.

Useful to check duplicates

List

enumerate allows you to get the index and the item easily.

1	for i, n in enumerate(nums):

Dropping list in-place can do

1
2
3

your_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
del your_list[5:] # Removes elements starting from index 5 (inclusive) till the end. 
your_list # now its [1, 2, 3, 4, 5, 6]

Linked List

Most questions are swapping questions.

Stack

List can be acted as a stack, using .pop() to throw away the last value

Dict

your_dict.get(item, 0) the 0 marks the default value if item is not found.

loop through dict is also easy

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    count = {}
    freq = [[] for i in range(len(nums) + 1)]

    for n in nums:
        count[n] = 1 + count.get(n, 0)
    for n, c in count.items():
        freq[c].append(n)

    res = []
    for i in range(len(freq)-1, 0, -1):
        for n in freq[i]:
            res.append(n)
            if len(res) == k:
                return res # O(n)

defaultdict

defaultdict streamline handling of missing keys by avoiding repetitive checks or KeyError handling.

1 2	d = defaultdict(list) d['fruits'].append('apple') # Automatically creates a list and adds 'apple'

Moreover it can handle tuples, unlike dict()

def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    res = defaultdict(list) # mapping charCount to list of Anagrams

    for s in strs:
        count = [0] * 26
        for c in s:
            # ord make ascii value 
            # ord("a") - ord("a") = 0
            count[ord(c) - ord("a")] += 1 
        res[tuple(count)].append(s) # List would cause errors because unhashable type
    return res.values()

English

Anagram: means two strings contain same number of characters. Can be solved by comparing two dicts, or even single defaultdict (using the difference properties)
Palindrome: means the inverted string would be the same. Can be solved by s[::-1]