Approach

  1. Try to solve the problem using brute force. This helps to come up with a logic required for the problem.
  2. Identify the pattern.
  3. Implement the solution using the pattern.
  4. Identify time and space complexity.

Tips to match the pattern

  1. If the problem involves exploring a search space in a tree or a graph then we can consider BFS or DFS.
    • If the problem requires minimum number of steps then we should use BFS instead of DFS to explore.

Patterns

Prefix

Problems

  • Subarray sum k
res = 0
presumToCount = defaultdict(int)
presum = 0
for num in nums:
    presum += num
    if presum == k:
        res += 1
    res += presumToCount[presum - k]
    presumToCount[presum] += 1
return res
  • 1915. Number of Wonderful Substrings
  • Similar to sub array sum equals k, but we use bitmask and xor operations on the prefix values to find the substrings with zero odd count (prefix is zero) and with 1 odd count.

Sliding window

Problems

Heap

Problems

BFS

  • Level order traversal is a version of BFS.
  • We can revisit a node based on a condition. Ex. 2092. Find All People With Secret

Problems

  • 752. Open the Lock

    • As we need minimum number of turns we should use BFS (Level order traversal)

  • 2092. Find All People With Secret

    • Revisit the node based if the secret is know to that node earliest. Revisit the node if better option is found in the later point.
    • Multi source bfs revisiting the nodes if better option is found.
     1q = deque()
 2q.append([0, 0])
 3q.append([0, firstPerson])
 4earliest = [inf] *  n
 5earliest[0] = 0
 6earliest[firstPerson] = 0
 7while q:
 8    time, u = q.popleft()
 9    for t, v in adj[u]:
10        if t >= time and t < earliest[v]:
11            earliest[v] = t
12            q.append([t, v])

DFS

  • Eulerian path here
  • Detecting cycle in directed graphhere

Problems

  • 834. Sum of Distances in Tree
    • Use recursion to find distances from root to all other nodes.
    • Use the root value to calculate the answer for the child.

Topological sort

Problems

Course sechdule II

adj = defaultdict(list)
for u, v in prerequisites:
    adj[u].append(v)

visiting = set()
finished = set()
order = []
def dfs(u):
    if u in visiting:
        return False
    
    if u in finished:
        return True
    
    visiting.add(u)
    for v in adj[u]:
        if not dfs(v):
            return False
    visiting.remove(u)
    finished.add(u)
    order.append(u)
    return True

for i in range(numCourses):
    if not dfs(i):
        return []

return order

in_degree = [0] * numCourses
adj = defaultdict(list)
for u, v in prerequisites:
    adj[u].append(v)
    in_degree[v] += 1

q = deque()
for i in range(numCourses):
    if in_degree[i] == 0:
        q.append(i)

res = []
while q:
    u = q.popleft()
    res.append(u)
    for v in adj[u]:
        in_degree[v] -= 1
        if in_degree[v] == 0:
            q.append(v)

return [] if len(res) != numCourses else res[::-1]

Dynammic programming

Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False

class Trie:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.endOfWord = True


    def search(self, word: str) -> bool:
        curr = self.root
        for c in word:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return curr.endOfWord

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for c in prefix:
            if c not in curr.children:
                return False
            curr = curr.children[c]
        return True

Problems