Depth-First Search (DFS) on Graphs

Problem: isConnected[i][j] = 1 means city i and city j are directly connected. A province is a group of cities connected directly or indirectly. Count the provinces.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 200 · n == isConnected.length · n == isConnected[i].length · isConnected[i][j] is 1 or 0. · isConnected[i][i] == 1 · isConnected[i][j] == isConnected[j][i]

From brute force to the pattern: Repeatedly merging groups of cities by scanning the matrix is slow and fiddly. One DFS (or union-find) per unvisited city visits each city once and reads its matrix row: O(n²), which is the size of the input.

Spot it: "groups connected directly or indirectly" = connected components. The input is an adjacency matrix.

Key insight: Loop over cities. Each time you find an unvisited one, that's a new province: DFS from it to chalk-mark every city in that province.

Approach:

1. Keep visited, a boolean per city.
2. Loop over every city u. If it's unvisited, that's a new province: add 1.
3. Run DFS from u: mark it, then recurse into every v with isConnected[u][v] == 1 that isn't visited yet.
4. When the loop ends, the counter is the number of provinces.

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        city_count = len(isConnected)
        # Save the input on self so the dfs method can read it.
        self.isConnected = isConnected
        self.visited = [False] * city_count  # one flag per city, all start False
        provinces = 0
        for city in range(city_count):
            if not self.visited[city]:
                provinces = provinces + 1  # fresh start = a new province
                self.dfs(city)             # chalk every city in this province
        return provinces

    # Mark city, then dive into every connected city we have not visited yet.
    def dfs(self, city: int) -> None:
        self.visited[city] = True
        row = self.isConnected[city]   # row[other] == 1 means city and other are connected
        for other in range(len(row)):
            if row[other] == 1 and not self.visited[other]:
                self.dfs(other)

What the code is doing, line by line:

1. findCircleNum stores the matrix and a visited list on self, so the separate dfs method can use them.
2. It loops over every city. An unvisited city means a new province: add 1 to provinces.
3. It then calls self.dfs(city), which marks every city in that province.
4. dfs marks the city, takes its matrix row, and for every other city with row[other] == 1 that isn't visited, dives into it.
5. When the outer loop ends, provinces holds the answer.

Dry run on isConnected = [[1,1,0],[1,1,0],[0,0,1]]:

Edge cases to test:

• No connections → n provinces.
• Everyone connected → 1.
• Indirect connections (A–B, B–C) form one province.

Complexity: O(n²) time (matrix input), O(n) space. Union-Find is an equally good alternative.

Problem: Given a reference to one node of a connected undirected graph, return a deep copy. Every node has val and a list of neighbors.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the graph is in the range [0, 100]. · 1 ≤ Node.val ≤ 100 · Node.val is unique for each node. · There are no repeated edges and no self-loops in the graph. · The Graph is connected and all nodes can be visited starting from the given node.

From brute force to the pattern: Copying recursively without remembering what's already copied loops forever on cycles (or duplicates nodes). The old → new map acts as both the visited set and the lookup table: O(V + E).

Spot it: "copy every node reachable from here", and the graph has cycles. That's DFS with a visited map.

Key insight: Use a dict original → clone as the visited set. Register the clone before recursing into neighbours. Otherwise a cycle (A ↔ B) would try to clone A again forever.

Approach:

1. Keep a dict copies mapping each original node to its clone. It doubles as the visited set.
2. dfs(u): if u is already in copies, return its clone.
3. Otherwise create the clone and store it in the dict before recursing.
4. Fill the clone's neighbours with dfs(v) for each original neighbour, then return the clone.

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if node is None:               # empty graph -> nothing to copy
            return None
        self.copies = {}               # original node -> its clone (also our "visited" set)
        return self.clone(node)

    # Return the clone of original, creating it (and its neighbours) if needed.
    def clone(self, original: 'Node') -> 'Node':
        if original in self.copies:    # already cloned: reuse it (this stops cycles)
            return self.copies[original]
        copy = Node(original.val)
        self.copies[original] = copy   # register BEFORE recursing, so A <-> B ends
        for neighbour in original.neighbors:
            neighbour_copy = self.clone(neighbour)
            copy.neighbors.append(neighbour_copy)
        return copy

What the code is doing, line by line:

1. If the input is None, there is nothing to copy.
2. Otherwise we create the dict self.copies (original → clone) and start cloning from the given node.
3. clone(original) first checks the dict. If this node was already cloned, it returns that clone. This is what stops the cycle A → B → A from going forever.
4. Otherwise it makes a new Node with the same value and stores it in the dict before touching neighbours.
5. Then for each original neighbour it gets (or makes) the neighbour's clone and appends it to the new node's neighbors list.

Dry run on adjList = [[2,4],[1,3],[2,4],[1,3]] (a square 1-2-3-4-1):

Edge cases to test:

• An empty graph (None) → None.
• A single node with no neighbours.
• Cycles in the graph.

Complexity: O(V + E) time, O(V) space.

Problem: There are numCourses courses. [a, b] means you must take b before a. Can you finish them all?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ numCourses ≤ 2000 · 0 ≤ prerequisites.length ≤ 5000 · prerequisites[i].length == 2 · 0 ≤ ai, bi < numCourses · All the pairs prerequisites[i] are unique.

From brute force to the pattern: Trying course orders is factorial. Cycle detection with a three-colour DFS (a gray node met again means a cycle) or Kahn's topological sort runs in O(V + E).

Spot it: "prerequisites" = a directed graph. You can finish everything if and only if there's no cycle.

Key insight: Three-colour DFS. A gray node is on the current path. If you reach a gray node again, you've found a loop of courses that all wait on each other.

Approach:

1. Build the graph with edges pre → course.
2. Colour every node WHITE (0).
3. has_cycle(u): paint u GRAY. For each neighbour, a GRAY one means a cycle; a WHITE one means recurse.
4. After all neighbours are done, paint u BLACK and return False (no cycle through u).
5. Run it from every WHITE node. The answer is True only if no call ever found a cycle.

class Solution:
    WHITE = 0   # never visited
    GRAY = 1    # on the current path
    BLACK = 2   # fully explored, known safe

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # graph[pre] = list of courses that need pre first (edge pre -> course)
        self.graph = {}
        for course in range(numCourses):
            self.graph[course] = []
        for pair in prerequisites:
            course = pair[0]
            pre = pair[1]
            self.graph[pre].append(course)
        self.color = [self.WHITE] * numCourses  # every course starts WHITE
        for course in range(numCourses):
            if self.color[course] == self.WHITE:
                if self.has_cycle(course):
                    return False       # a loop of courses waiting on each other
        return True

    # Returns True if a cycle can be reached from course.
    def has_cycle(self, course: int) -> bool:
        self.color[course] = self.GRAY  # course is on the current path
        for next_course in self.graph[course]:
            if self.color[next_course] == self.GRAY:  # back edge -> cycle
                return True
            if self.color[next_course] == self.WHITE:
                if self.has_cycle(next_course):
                    return True
        self.color[course] = self.BLACK  # finished without finding a cycle
        return False

What the code is doing, line by line:

1. Three class-level names WHITE, GRAY, BLACK make the colours readable (self.GRAY instead of a bare 1).
2. We build self.graph: every course gets an empty list, then each pair [course, pre] adds the edge pre → course.
3. Every course starts WHITE. We call has_cycle on each course that is still WHITE. If any call finds a cycle, the answer is False.
4. has_cycle paints the course GRAY (it is on our current path), then checks each course that depends on it.
5. A GRAY next course means we came back to our own path: cycle, return True. A WHITE one is explored recursively.
6. If all next courses are fine, the course is painted BLACK (safe) and we return False.

Dry run on example 2, numCourses = 2, prerequisites = [[1,0],[0,1]] (graph {0: [1], 1: [0]}):

With example 1 ([[1,0]]) the same steps paint 1 then 0 BLACK and the answer is True.

Edge cases to test:

• No prerequisites → True.
• A self-loop like [0, 0] → False.
• Several disconnected groups of courses.

Complexity: O(V + E) time and space.

Problem: Same input as 207, but return an order in which to take all courses, or [] if that's impossible.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ numCourses ≤ 2000 · 0 ≤ prerequisites.length ≤ numCourses * (numCourses - 1) · prerequisites[i].length == 2 · 0 ≤ ai, bi < numCourses · ai != bi · All the pairs [ai, bi] are distinct.

From brute force to the pattern: Generating orders and checking them is factorial. A topological sort produces a valid order (or detects a cycle) in O(V + E).

Spot it: "return an ordering that respects dependencies" = topological sort.

Key insight: In DFS, a course turns black only after every course that depends on it has turned black. So the finish order lists dependents first. Reverse it to put prerequisites first.

Approach:

1. Build the graph pre → course and colour every node WHITE.
2. visit(u): paint it GRAY and explore its neighbours. If you hit a GRAY node, report a cycle.
3. When u finishes, paint it BLACK and append it to post.
4. Visit every WHITE node. If any cycle was found, return [].
5. Return post reversed. Every course now comes after all of its prerequisites.

class Solution:
    WHITE = 0   # never visited
    GRAY = 1    # on the current path
    BLACK = 2   # finished

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # graph[pre] = list of courses that need pre first (edge pre -> course)
        self.graph = {}
        for course in range(numCourses):
            self.graph[course] = []
        for pair in prerequisites:
            course = pair[0]
            pre = pair[1]
            self.graph[pre].append(course)
        self.color = [self.WHITE] * numCourses
        self.post = []                 # courses in the order they FINISH
        for course in range(numCourses):
            if self.color[course] == self.WHITE:
                if not self.visit(course):
                    return []          # cycle -> impossible
        # Reverse the finish order (prerequisites end up first).
        order = []
        i = len(self.post) - 1
        while i >= 0:
            order.append(self.post[i])
            i = i - 1
        return order

    # Returns False if a cycle is found below course.
    def visit(self, course: int) -> bool:
        self.color[course] = self.GRAY
        for next_course in self.graph[course]:
            if self.color[next_course] == self.GRAY:
                return False           # cycle
            if self.color[next_course] == self.WHITE:
                if not self.visit(next_course):
                    return False
        self.color[course] = self.BLACK
        self.post.append(course)       # finished: everything after it is placed
        return True

What the code is doing, line by line:

1. Same graph as 207: every course gets a list, and each pair [course, pre] adds pre → course.
2. self.color starts all WHITE and self.post (finish order) starts empty.
3. We call visit on every WHITE course. If it returns False a cycle exists, so we return [].
4. visit paints the course GRAY, explores each next course (GRAY = cycle, WHITE = recurse), then paints it BLACK and appends it to post.
5. At the end we copy post backwards with a while loop. Courses that finish last (the ones with no prerequisites) come out first.

Dry run on numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] (graph {0: [1, 2], 1: [3], 2: [3], 3: []}):

Edge cases to test:

• A cycle → [].
• No prerequisites → any order of all courses.
• Isolated courses must still appear in the answer.

Complexity: O(V + E) time and space.

Problem: n servers and undirected connections. A connection is critical if removing it disconnects some servers. Return all critical connections (these are called bridges).

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 10⁵ · n - 1 ≤ connections.length ≤ 10⁵ · 0 ≤ ai, bi ≤ n - 1 · ai != bi · There are no repeated connections.

From brute force to the pattern: Removing each edge and checking connectivity is O(E · (V + E)). Tarjan's bridge-finding DFS identifies every critical edge in one pass: O(V + E).

Spot it: "removing an edge disconnects the graph" = bridges, which Tarjan's DFS finds in one pass.

Key insight: Stamp each node with its discovery time disc[u]. Let low[u] be the earliest discovery time reachable from u's DFS subtree using one back edge. If a child v can't reach anything discovered at or before u (low[v] > disc[u]), the only way out of v's subtree is the edge u–v, so it's a bridge. An edge on a cycle is never a bridge.

Approach:

1. Build an undirected adjacency list. disc[u] = -1 marks unvisited.
2. DFS from node 0, giving each node a discovery time disc[u] and starting with low[u] = disc[u].
3. For each neighbour v other than the parent: if unvisited, recurse, then set low[u] = min(low[u], low[v]).
4. Right after recursing into v: if low[v] > disc[u], nothing in v's subtree can reach u or above without the edge u–v, so it's a bridge.
5. If v was already visited (a back edge), set low[u] = min(low[u], disc[v]).

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        # Undirected adjacency list: add each connection in both directions.
        self.graph = {}
        for server in range(n):
            self.graph[server] = []
        for connection in connections:
            server_a = connection[0]
            server_b = connection[1]
            self.graph[server_a].append(server_b)
            self.graph[server_b].append(server_a)
        self.disc = [-1] * n           # discovery time (-1 = not visited yet)
        self.low = [0] * n             # earliest disc reachable from the subtree
        self.bridges = []
        self.timer = 0                 # the next discovery time to hand out
        self.dfs(0, -1)                # the network is connected; 0 has no parent
        return self.bridges

    def dfs(self, node: int, parent: int) -> None:
        self.disc[node] = self.timer   # stamp the discovery time
        self.low[node] = self.timer    # at first, node can only reach itself
        self.timer = self.timer + 1
        for neighbour in self.graph[node]:
            if neighbour == parent:
                continue               # don't use the edge we came in on
            if self.disc[neighbour] == -1:  # tree edge: explore it
                self.dfs(neighbour, node)
                self.low[node] = min(self.low[node], self.low[neighbour])
                if self.low[neighbour] > self.disc[node]:
                    # neighbour's subtree can't climb above node -> bridge
                    self.bridges.append([node, neighbour])
            else:                      # back edge to an ancestor
                self.low[node] = min(self.low[node], self.disc[neighbour])

What the code is doing, line by line:

1. We build an undirected adjacency list on self.graph (each connection added both ways).
2. self.disc holds each server's discovery time (-1 = not visited). self.low holds the earliest discovery time the server's subtree can reach. self.timer is the next time stamp.
3. We start dfs(0, -1): server 0 with no parent.
4. In dfs, we stamp disc and low with the timer and move the timer on.
5. For each neighbour: skip the parent (that's the edge we came in on). An unvisited neighbour is a tree edge: recurse, then pull its low up into ours. If low[neighbour] > disc[node], the neighbour's subtree has no other way back, so the edge is a bridge.
6. A visited neighbour that isn't the parent is a back edge: it lets us reach disc[neighbour], so low[node] may drop to that.

Dry run on n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] (graph {0: [1, 2], 1: [0, 2, 3], 2: [1, 0], 3: [1]}):

(low[3] shows 0 before 3 is entered only because low starts as all zeros; it is overwritten when 3 is discovered.)

Edge cases to test:

• A tree (every edge is critical).
• One big cycle → [].
• Ignore the edge back to your DFS parent when updating low.

Complexity: O(V + E) time and space. For n = 105 in Python, raise the recursion limit or convert to an iterative DFS.

Problem: Given n nodes and an undirected edge list, is there a path from source to destination?

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ n ≤ 2 * 10⁵ · 0 ≤ edges.length ≤ 2 * 10⁵ · edges[i].length == 2 · 0 ≤ ui, vi ≤ n - 1 · ui != vi · 0 ≤ source, destination ≤ n - 1 · There are no duplicate edges. · There are no self edges.

From brute force to the pattern: Trying every path is exponential. A traversal visits each vertex and edge once: O(V + E). Union-find is another good option.

Spot it: "is there a path" is plain reachability. DFS from the source and see if you reach the destination.

Approach:

1. Build an adjacency list (both directions).
2. Push source onto a stack and mark it seen.
3. Pop a node. If it's the destination, return True. Otherwise push its unseen neighbours, marking them as you push.
4. If the stack empties first, return False.

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = {}
        for node in range(n):
            graph[node] = []
        for edge in edges:
            node_a = edge[0]
            node_b = edge[1]
            graph[node_a].append(node_b)
            graph[node_b].append(node_a)   # undirected: add both directions
        seen = set()
        seen.add(source)
        stack = [source]               # a plain list used as a stack
        while len(stack) > 0:
            node = stack.pop()         # pop() takes the newest item off the top
            if node == destination:
                return True
            for neighbour in graph[node]:
                if neighbour not in seen:
                    seen.add(neighbour)    # mark when pushed: never pushed twice
                    stack.append(neighbour)
        return False                   # stack empty: destination never reached

What the code is doing, line by line:

1. Build the adjacency list: every node gets an empty list, then each edge is added in both directions.
2. Put source in seen and on the stack.
3. While the stack isn't empty, pop the top node. If it is the destination, we found a path: return True.
4. Otherwise push every neighbour we haven't seen, marking it as seen at push time so it is never pushed twice.
5. If the stack runs out, the destination is unreachable: return False.

Dry run on n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 (graph {0: [1, 2], 1: [0, 2], 2: [1, 0]}):

Edge cases to test:

• source == destination → True.
• No edges at all.
• Disconnected components.

Complexity: O(V + E) time and space.

Problem: Room 0 is unlocked, and every other room is locked. rooms[i] lists the keys you find inside room i. Can you get into every room?

Solve it on LeetCode ↗

Constraints: n == rooms.length · 2 ≤ n ≤ 1000 · 0 ≤ rooms[i].length ≤ 1000 · 1 ≤ sum(rooms[i].length) ≤ 3000 · 0 ≤ rooms[i][j] < n · All the values of rooms[i] are unique.

From brute force to the pattern: Repeatedly scanning all rooms for ones you can now open is O(n²). A single DFS/BFS from room 0 over the key graph is O(rooms + keys).

Spot it: Rooms are nodes and keys are directed edges. "Can I visit all?" means: does a DFS from room 0 reach every node?

Approach:

1. Start with seen = {0} and a stack [0].
2. Pop a room, and for each key that opens an unseen room, mark that room and push it.
3. At the end, compare the number of rooms seen with the total.

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        seen = set()
        seen.add(0)                    # room 0 is unlocked
        stack = [0]                    # rooms we can enter but have not searched yet
        while len(stack) > 0:
            room = stack.pop()         # pop() takes the newest room off the top
            for key in rooms[room]:    # each key = an edge room -> key
                if key not in seen:
                    seen.add(key)
                    stack.append(key)
        return len(seen) == len(rooms)  # did we reach every room?

What the code is doing, line by line:

1. Room 0 is open, so it starts in seen and on the stack.
2. Pop a room and look at each key inside it.
3. A key to a room we haven't seen: mark that room seen and push it so we search it later.
4. When the stack is empty we have searched every room we can open. Compare how many we saw with the total.

Dry run on rooms = [[1],[2],[3],[]]:

4 rooms seen out of 4, so the answer is True.

Edge cases to test:

• Room 0 contains no keys.
• Keys to rooms that are already open.
• A key to room 0 itself.

Complexity: O(rooms + keys) time, O(rooms) space.

Problem: Given a DAG (directed graph with no cycles) as an adjacency list, return every path from node 0 to node n-1.

Solve it on LeetCode ↗

Constraints: n == graph.length · 2 ≤ n ≤ 15 · 0 ≤ graph[i][j] < n · graph[i][j] != i (i.e., there will be no self-loops). · All the elements of graph[i] are unique. · The input graph is guaranteed to be a DAG.

From brute force to the pattern: There's no shortcut: the output itself can be exponential in size. Backtracking enumerates each path exactly once without needing a visited set, because there are no cycles.

Spot it: "all paths" means explore every branch, which is DFS. The graph has no cycles, so no visited set is needed.

Approach:

1. Keep the current path (it starts as [0]).
2. dfs(u): if u is the target, save a copy of the path.
3. Otherwise, for each neighbour v: append it, recurse, then pop it (undo, backtracking-style).

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        self.graph = graph
        self.target = len(graph) - 1
        self.result = []
        self.path = [0]                # the path we are walking right now
        self.dfs(0)
        return self.result

    def dfs(self, node: int) -> None:
        if node == self.target:
            path_copy = list(self.path)  # copy! self.path keeps changing afterwards
            self.result.append(path_copy)
            return
        for next_node in self.graph[node]:
            self.path.append(next_node)  # choose
            self.dfs(next_node)          # explore
            self.path.pop()              # un-choose (backtrack)

What the code is doing, line by line:

1. allPathsSourceTarget saves the graph, the target n-1, an empty result and the current path = [0] on self, then calls dfs(0).
2. In dfs, if we are at the target, we append a copy of the path (list(self.path)). Without the copy, later pop() calls would change the saved path too.
3. Otherwise for each next node: append it to the path (choose), recurse (explore), then pop it off again (un-choose) so the path is ready for the next branch.
4. No visited set: the graph is a DAG, so we can never loop.

Dry run on graph = [[1,2],[3],[3],[]] (target = 3):

Edge cases to test:

• A direct edge from 0 to n − 1.
• Several paths that share a prefix.
• A node with no outgoing edges.

Complexity: O(2n · n) in the worst case, since there can be exponentially many paths. Extra space is O(n) on top of the output.

Problem: In a directed graph, a node is safe if every path starting from it ends at a terminal node (one with no outgoing edges). Return all safe nodes in sorted order.

Solve it on LeetCode ↗

Constraints: n == graph.length · 1 ≤ n ≤ 10⁴ · 0 ≤ graph[i].length ≤ n · 0 ≤ graph[i][j] ≤ n - 1 · graph[i] is sorted in a strictly increasing order. · The graph may contain self-loops. · The number of edges in the graph will be in the range [1, 4 * 10⁴].

From brute force to the pattern: Exploring all paths from every node is exponential. Colouring nodes once (unvisited / in progress / safe) gives each node's status in O(V + E).

Spot it: A node is unsafe exactly when it can reach a cycle. That's 3-colour DFS, and the final colours give the answer.

Approach:

1. color[u]: 0 = unvisited, 1 = GRAY (on the path, or proven unsafe), 2 = BLACK (safe).
2. safe(u): if it's already coloured, return color[u] == 2.
3. Otherwise paint it GRAY and check every neighbour. If any neighbour is unsafe, return False and leave u GRAY, so it stays marked unsafe.
4. If every neighbour is safe, paint u BLACK and return True.
5. Return every u in 0..n-1 with safe(u) True.

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        node_count = len(graph)
        self.graph = graph
        self.color = [0] * node_count  # 0 white, 1 gray/unsafe, 2 black/safe
        safe_nodes = []
        for node in range(node_count):  # 0..n-1 in order, so the answer is sorted
            if self.safe(node):
                safe_nodes.append(node)
        return safe_nodes

    def safe(self, node: int) -> bool:
        if self.color[node] != 0:      # already decided (or on the current path)
            return self.color[node] == 2  # gray here = on a cycle (or leads to one)
        self.color[node] = 1           # gray: on the current path
        for next_node in self.graph[node]:
            if not self.safe(next_node):
                return False           # node stays GRAY forever = unsafe
        self.color[node] = 2           # every path from node ends at a terminal node
        return True

What the code is doing, line by line:

1. self.color starts all 0 (white). We ask safe(node) for every node in order, and keep the safe ones. Going 0, 1, 2... means the answer comes out sorted.
2. In safe, a node that already has a colour is answered at once: BLACK (2) means safe, GRAY (1) means it is on a cycle or leads to one.
3. Otherwise we paint it GRAY and check every next node. If any of them is unsafe, we return False and leave this node GRAY on purpose: GRAY now also means "unsafe".
4. If every next node is safe, the node is painted BLACK and we return True.

Dry run on graph = [[1,2],[2,3],[5],[0],[5],[],[]]:

Answer: [2, 4, 5, 6].

Edge cases to test:

• Terminal nodes (no outgoing edges) are safe.
• Self-loops are unsafe.
• A node that can reach a cycle is unsafe even if some of its paths end.

Complexity: O(V + E) time and space.

Problem: You're given equations like a / b = 2.0. Answer queries like a / c. Return -1.0 if a query can't be determined.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ equations.length ≤ 20 · equations[i].length == 2 · 1 ≤ Ai.length, Bi.length ≤ 5 · values.length == equations.length · 0.0 < values[i] ≤ 20.0 · 1 ≤ queries.length ≤ 20 · queries[i].length == 2 · 1 ≤ Cj.length, Dj.length ≤ 5 · Ai, Bi, Cj, Dj consist of lower case English letters and digits.

From brute force to the pattern: Trying to solve the equations algebraically is complicated. Modelling the equations as a weighted graph and multiplying along a DFS path answers each query in O(V + E).

Spot it: Variables are nodes, and a/b = k is an edge a→b with weight k (plus b→a with weight 1/k). A query is "find any path and multiply the weights along it", which DFS can do.

Approach:

1. Build a weighted graph: graph[a][b] = k and graph[b][a] = 1/k.
2. For each query (x, y): if either variable is unknown, the answer is -1.
3. Otherwise DFS from x with a fresh visited set. When you reach y, return 1.
4. On the way back up, multiply by each edge's weight. If no neighbour leads to y, return -1.

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float],
                     queries: List[List[str]]) -> List[float]:
        # graph[a][b] = the value of a / b
        self.graph = {}
        for i in range(len(equations)):
            top = equations[i][0]
            bottom = equations[i][1]
            value = values[i]
            if top not in self.graph:
                self.graph[top] = {}
            if bottom not in self.graph:
                self.graph[bottom] = {}
            self.graph[top][bottom] = value      # top / bottom = value
            self.graph[bottom][top] = 1 / value  # bottom / top = 1 / value
        answers = []
        for query in queries:
            start = query[0]
            target = query[1]
            if start in self.graph and target in self.graph:
                answers.append(self.dfs(start, target, set()))
            else:
                answers.append(-1.0)   # unknown variable
        return answers

    # Returns node / target by walking a path, or -1.0 if there is no path.
    def dfs(self, node: str, target: str, seen: set) -> float:
        if node == target:
            return 1.0                 # x / x = 1
        seen.add(node)
        for neighbour in self.graph[node]:
            if neighbour not in seen:
                rest = self.dfs(neighbour, target, seen)
                if rest != -1.0:
                    weight = self.graph[node][neighbour]  # node / neighbour
                    return weight * rest  # node/target = (node/neighbour) * (neighbour/target)
        return -1.0

What the code is doing, line by line:

1. We build self.graph as a dict of dicts. For top / bottom = value we store graph[top][bottom] = value and the reverse graph[bottom][top] = 1 / value. Each variable's inner dict is created the first time we see it.
2. For each query [start, target]: if either variable never appeared in an equation, the answer is -1.0.
3. Otherwise we call dfs(start, target, set()) with a fresh seen set.
4. In dfs: reaching the target returns 1.0. Otherwise we mark the node seen and try each unseen neighbour. If a neighbour finds the target (rest != -1.0), we multiply by the edge weight on the way back: node/target = (node/neighbour) × (neighbour/target).
5. If no neighbour leads to the target, return -1.0.

Dry run on a/b = 2, b/c = 3 (graph {a: {b: 2.0}, b: {a: 0.5, c: 3.0}, c: {b: 0.333}}):

Edge cases to test:

• A variable that never appears → −1.0.
• x / x for a known variable → 1.0.
• Variables in different components → −1.0.

Complexity: O(Q · (V + E)) time, O(V + E) space.

Problem: Given airline tickets [from, to], use every ticket exactly once to build an itinerary starting at "JFK". If several work, return the lexicographically smallest one.

Solve it on LeetCode ↗

Constraints: 1 ≤ tickets.length ≤ 300 · tickets[i].length == 2 · fromi.length == 3 · toi.length == 3 · fromi and toi consist of uppercase English letters. · fromi != toi

From brute force to the pattern: Backtracking over ticket orders can be exponential. Hierholzer's algorithm (with sorted destinations, consumed as you go) builds the itinerary in O(E log E).

Spot it: "use every edge exactly once" is an Euler path. Hierholzer's algorithm is a DFS that adds a node to the route when it gets stuck (postorder).

Approach:

1. Build adjacency lists sorted in reverse order, so pop() always returns the smallest destination.
2. visit(a): while a still has unused tickets, pop the smallest destination and visit it. Popping uses up the ticket.
3. When a has no tickets left, append a to route (postorder).
4. Dead ends get appended first, so reverse route at the end.

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        # Sort tickets from LARGEST to smallest, so that when we append them,
        # the smallest destination ends up LAST in each list and pop() returns it.
        sorted_tickets = sorted(tickets, reverse=True)
        self.graph = {}
        for ticket in sorted_tickets:
            start = ticket[0]
            end = ticket[1]
            if start not in self.graph:
                self.graph[start] = []
            if end not in self.graph:
                self.graph[end] = []   # every airport gets a list, even with no tickets out
            self.graph[start].append(end)
        self.route = []
        self.visit("JFK")
        # Dead ends were added first, so reverse the route with a while loop.
        answer = []
        i = len(self.route) - 1
        while i >= 0:
            answer.append(self.route[i])
            i = i - 1
        return answer

    def visit(self, airport: str) -> None:
        while len(self.graph[airport]) > 0:   # tickets still unused from here
            next_airport = self.graph[airport].pop()  # pop() uses up the ticket
            self.visit(next_airport)
        self.route.append(airport)     # stuck -> add in POSTorder

What the code is doing, line by line:

1. We sort the tickets from largest to smallest. Appending in that order puts the smallest destination at the end of each list, where pop() takes from.
2. We build self.graph: each airport gets a list (even airports with no tickets out), and each ticket appends its destination.
3. visit(airport): while this airport still has unused tickets, pop the smallest destination (this uses the ticket up) and visit it.
4. When an airport has no tickets left, we are stuck there, so we append it to self.route. This is post-order: the final stop is appended first.
5. Finally we copy self.route backwards with a while loop to get the itinerary from JFK.

Dry run on [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]:

Edge cases to test:

• A dead end reached early (that's why airports are added on the way back).
• Duplicate tickets.
• Lexicographic ties.

Complexity: O(E log E) time (sorting), O(E) space.

Problem: Return the length of the longest strictly increasing path in a grid, moving up, down, left or right.

Solve it on LeetCode ↗

Constraints: m == matrix.length · n == matrix[i].length · 1 ≤ m, n ≤ 200 · 0 ≤ matrix[i][j] ≤ 2³¹ - 1

From brute force to the pattern: DFS from every cell without memory recomputes the same paths over and over (exponential). The "strictly increasing" rule means there are no cycles, so caching each cell's answer makes it O(r · c).

Spot it: Edges go only from smaller to larger values, so the grid is an implicit DAG with no cycles. DFS from each cell, with memoization so each cell is computed once.

Approach:

1. dfs(r, c) = length of the longest increasing path starting at (r, c).
2. It's 1 + max(dfs(neighbour)) over the in-bounds neighbours with a larger value, or 1 if there are none.
3. Cache the results in a dict self.memo keyed by (row, col). No visited set is needed, because "strictly increasing" rules out cycles.
4. Return the maximum of dfs over all cells.

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        self.matrix = matrix
        self.rows = len(matrix)
        self.cols = len(matrix[0])
        self.memo = {}                 # (row, col) -> answer, so each cell is solved once
        best = 0
        for row in range(self.rows):
            for col in range(self.cols):
                length = self.dfs(row, col)
                if length > best:
                    best = length
        return best

    # Length of the longest increasing path that STARTS at (row, col).
    def dfs(self, row: int, col: int) -> int:
        if (row, col) in self.memo:    # solved before: reuse the answer
            return self.memo[(row, col)]
        best = 1                       # the cell by itself
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]  # down, up, right, left
        for direction in directions:
            next_row = row + direction[0]
            next_col = col + direction[1]
            inside = 0 <= next_row < self.rows and 0 <= next_col < self.cols
            if inside and self.matrix[next_row][next_col] > self.matrix[row][col]:
                candidate = 1 + self.dfs(next_row, next_col)  # strictly larger = no cycles
                if candidate > best:
                    best = candidate
        self.memo[(row, col)] = best   # remember it for next time
        return best

What the code is doing, line by line:

1. longestIncreasingPath saves the matrix, its size and an empty self.memo dict on self.
2. It calls dfs(row, col) for every cell and keeps the largest result in best.
3. In dfs, if (row, col) is already in the memo, we return the saved answer: each cell is solved only once.
4. Otherwise best = 1 (the cell alone). For each of the 4 directions we compute the neighbour's row and column, check it is inside the grid and strictly larger, and if so try 1 + dfs(neighbour).
5. We save the best length in the memo before returning it. No visited set is needed: values must strictly increase, so a path can't loop.

Dry run on matrix = [[9,9,4],[6,6,8],[2,1,1]] (cells in the order they get solved):

The largest value is 4 (path 1 → 2 → 6 → 9).

Edge cases to test:

• All values equal → 1.
• A single cell → 1.
• A long snake-shaped increasing path.

Complexity: O(R·C) time and space.

Problem: Return True if some root-to-leaf path has values adding up to targetSum.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [0, 5000]. · -1000 ≤ Node.val ≤ 1000 · -1000 ≤ targetSum ≤ 1000

From brute force to the pattern: Collecting every root-to-leaf path and summing it is O(n · h). Passing the remainder down checks each path as you reach its leaf: O(n).

Spot it: Root-to-leaf paths → DFS that carries state downward. Subtracting each node's value from the target means a leaf only has to check whether what is left equals its own value.

Approach:

1. An empty tree has no paths: False.
2. Subtract the current node's value from the remaining sum.
3. At a leaf (no children), succeed if the remainder is exactly 0.
4. Otherwise succeed if either child's subtree has a path for the new remainder.

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False
        remaining = targetSum - root.val
        if root.left is None and root.right is None:
            # a leaf: the path ends here, so nothing may be left over
            return remaining == 0
        # keep going down either side with what is still needed
        return self.hasPathSum(root.left, remaining) or self.hasPathSum(root.right, remaining)

What the code is doing, line by line:

1. if root is None: return False: reached from a node with only one child. That is not a leaf, so no valid path ends here.
2. remaining = targetSum - root.val: how much the rest of the path must still add up to.
3. if root.left is None and root.right is None: the path must end at a leaf, so check the remainder only here.
4. return ... or ...: try the left subtree, and only if that fails, the right one.

Dry run on the example:

root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22 (LeetCode Example 1). Returns True via 5 → 4 → 11 → 2.

Edge cases to test:

• An empty tree → False, even if targetSum = 0.
• A node with one child is not a leaf.
• Negative values.

Complexity: O(n) time, O(h) recursion space.

Problem: Each node holds a digit 0..9, and every root-to-leaf path spells a number (1 → 2 → 3 is 123). Return the sum of all these numbers.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the tree is in the range [1, 1000]. · 0 ≤ Node.val ≤ 9 · The depth of the tree will not exceed 10.

From brute force to the pattern: Building each path as a string and converting it is O(n · h). Carrying the number down computes each path's value incrementally: O(n).

Spot it: Root-to-leaf + state that accumulates on the way down → DFS passing the partial number to the children.

Approach:

1. dfs(node, number) receives the number formed by the path above node.
2. Append this digit: number = number * 10 + node.val.
3. At a leaf, the path's number is complete: return it.
4. Otherwise return the sum of both children's results (a missing child contributes 0).

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, number):
            if node is None:
                return 0
            # shift the digits left and append this node's digit
            number = number * 10 + node.val
            if node.left is None and node.right is None:
                return number            # a complete root-to-leaf number
            return dfs(node.left, number) + dfs(node.right, number)

        return dfs(root, 0)

What the code is doing, line by line:

1. def dfs(node, number): number is passed by value, so each branch builds its own copy. No undoing is needed.
2. if node is None: return 0: a missing child adds nothing.
3. number = number * 10 + node.val: e.g. 12 followed by digit 3 → 123.
4. if node.left is None and node.right is None: return number: a leaf finishes one number.
5. return dfs(node.left, number) + dfs(node.right, number): add up every number below this node.

Dry run on the example:

root = [4, 9, 0, 5, 1] (LeetCode Example 2). Returns 1026 (= 495 + 491 + 40).

Edge cases to test:

• A single node.
• Nodes with value 0 inside a path.
• A node with one child.

Complexity: O(n) time, O(h) recursion space.

Problem: A node is good if no node on the path from the root to it has a greater value. Count the good nodes.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: The number of nodes in the binary tree is in the range [1, 10^5]. · Each node's value is between [-10^4, 10^4].

From brute force to the pattern: For each node, walking back up to the root is O(n · h). Carrying the path maximum down decides each node in O(1): O(n).

Spot it: "Compared with everything on the path from the root" → DFS that carries the largest value seen so far.

Approach:

1. dfs(node, max_so_far): max_so_far is the largest value on the path above node.
2. If node.val >= max_so_far, this node is good: count 1.
3. Update the maximum and add the counts from both children.
4. Start with dfs(root, root.val): the root is always good.

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, max_so_far):
            if node is None:
                return 0
            good = 0
            if node.val >= max_so_far:
                good = 1                      # nothing above it is bigger
            new_max = max(max_so_far, node.val)
            return good + dfs(node.left, new_max) + dfs(node.right, new_max)

        return dfs(root, root.val)

What the code is doing, line by line:

1. def dfs(node, max_so_far): each call knows the biggest value between the root and this node.
2. if node.val >= max_so_far: good = 1: equal values still count as good ("no node greater").
3. new_max = max(max_so_far, node.val): the path's maximum including this node, passed to both children.
4. return good + dfs(...) + dfs(...): this node's contribution plus everything below it.

Dry run on the example:

root = [3, 1, 4, 3, null, 1, 5] (LeetCode Example 1). Returns 4 (the nodes 3, 3, 4, 5).

Four yes rows → 4.

Edge cases to test:

• A single node → 1.
• Equal values count as good.
• Negative values.

Complexity: O(n) time, O(h) recursion space.

Problem: Return 1..n in lexicographical (dictionary) order in O(n) time and O(1) extra space.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 5 * 10⁴

From brute force to the pattern: sorted(range(1, n + 1), key=str) is O(n log n). Walking the prefix tree is O(n).

Spot it: Numbers form a prefix tree: 1 → 10..19 → 100..199 … Dictionary order is a pre-order DFS of it. Without recursion: from cur, go to its first child cur·10 if ≤ n; otherwise move to the next sibling cur + 1, climbing up (//10) while cur ends in 9 or cur + 1 > n.

Why not another pattern? Sorting the numbers as strings is O(n log n) and uses O(n) extra space.

Approach:

1. cur = 1; repeat n times: output cur.
2. If cur · 10 ≤ n, go down: cur *= 10.
3. Else: while cur % 10 == 9 or cur + 1 > n, go up: cur //= 10. Then cur += 1.

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []
        cur = 1
        for _ in range(n):
            result.append(cur)
            if cur * 10 <= n:
                cur = cur * 10  # first child: append a 0
            else:
                while cur % 10 == 9 or cur + 1 > n:
                    cur = cur // 10  # no next sibling here: climb up
                cur = cur + 1  # next sibling
        return result

What the code is doing, line by line:

1. Going to cur · 10 first is pre-order: a prefix comes before everything that extends it.
2. cur + 1 is the next sibling unless cur ends in 9 (the last child) or exceeds n.
3. Climbing with // 10 returns to the parent, whose next sibling is then taken.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n < 10 → just 1..n.
• Climbing over several 9s (e.g. after 199).
• n is itself a power of 10.

Complexity: O(n) time (each climb is paid for by earlier descents), O(1) extra space besides the output.

Problem: nums is a permutation of 1..n; each sequence in sequences is a subsequence of it. Return whether nums is the only shortest sequence having every sequence as a subsequence.

Solve it on LeetCode ↗ (Premium)

Constraints: n == nums.length · 1 ≤ n ≤ 10⁴ · nums is a permutation of all the integers in the range [1, n] · 1 ≤ sequences.length ≤ 10⁴ · 1 ≤ sum(sequences[i].length) ≤ 10⁵ · 1 ≤ sequences[i][j] ≤ n · All the arrays of sequences are unique · sequences[i] is a subsequence of nums

From brute force to the pattern: Listing all topological orders is exponential. Checking that Kahn's queue never holds two nodes is linear.

Spot it: Neighbouring numbers in each sequence give "comes before" edges. nums is the unique answer iff the topological order is forced at every step: Kahn's algorithm must always have exactly one node available, and it must be the next number of nums.

Why not another pattern? Generating every topological order to see if there's only one is exponential.

Approach:

1. Build edges a → b for neighbouring pairs in each sequence; count in-degrees.
2. Start Kahn's algorithm with the in-degree-0 nodes.
3. At each step: if the queue has more than one node, the order isn't unique → false. Pop it; it must equal nums[i].
4. Return true if all n numbers were placed.

from collections import deque

class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        n = len(nums)
        graph = [set() for _ in range(n + 1)]
        indegree = [0] * (n + 1)
        for seq in sequences:
            for a, b in zip(seq, seq[1:]):
                if b not in graph[a]:
                    graph[a].add(b)  # a must come before b
                    indegree[b] += 1
        queue = deque(v for v in range(1, n + 1) if indegree[v] == 0)
        i = 0
        while queue:
            if len(queue) > 1:
                return False  # two choices for the next number: not unique
            v = queue.popleft()
            if v != nums[i]:
                return False
            i = i + 1
            for w in graph[v]:
                indegree[w] -= 1
                if indegree[w] == 0:
                    queue.append(w)
        return i == n

What the code is doing, line by line:

1. Every adjacent pair in a sequence is a hard ordering rule.
2. With two nodes free at once, either could come first, so there are at least two valid supersequences.
3. A single choice each time means the order is forced; it must also match nums exactly.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Two numbers never ordered relative to each other → false.
• n = 1.
• Duplicate pairs across sequences (count each edge once).

Complexity: O(n + total sequence length) time and space.

Problem: From index start you may jump to i + arr[i] or i − arr[i] (staying inside the array). Can you reach any index with value 0?

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 5 * 10⁴ · 0 ≤ arr[i] < arr.length · 0 ≤ start < arr.length

From brute force to the pattern: Trying all jump sequences without memory can loop forever; a visited set makes it O(n).

Spot it: Each index has at most two moves: an implicit graph. Reachability is a DFS (or BFS) with a visited set.

Why not another pattern? Greedy (always jump one way) can miss paths; DP doesn't fit because moves go both left and right (cycles).

Approach:

1. Stack with start; seen set.
2. Pop i; if arr[i] == 0 return true.
3. Push i + arr[i] and i − arr[i] if inside the array and unseen.
4. Return false when the stack empties.

class Solution:
    def canReach(self, arr: List[int], start: int) -> bool:
        stack = [start]
        seen = {start}
        while stack:
            i = stack.pop()
            if arr[i] == 0:
                return True  # reached a zero
            for j in (i + arr[i], i - arr[i]):  # the two possible jumps
                if 0 <= j < len(arr) and j not in seen:
                    seen.add(j)
                    stack.append(j)
        return False

What the code is doing, line by line:

1. seen prevents bouncing between the same indices forever.
2. Indices are marked when pushed, so each is processed at most once.
3. If the stack empties without meeting a 0, no reachable index has value 0.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• arr[start] == 0 → true immediately.
• Jumps that leave the array.
• Two indices jumping to each other (a cycle).

Complexity: O(n) time and space.

Problem: News spreads from headID down the management tree; employee i takes informTime[i] to inform all direct reports. Return the total time.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁵ · 0 ≤ headID < n · manager.length == n · 0 ≤ manager[i] < n · manager[headID] == -1 · informTime.length == n · 0 ≤ informTime[i] ≤ 1000 · informTime[i] == 0 if employee i has no subordinates. · It is guaranteed that all the employees can be informed.

From brute force to the pattern: Walking each employee up to the head and summing costs is O(n · depth); one DFS down is O(n).

Spot it: Reports are informed in parallel, so the total time is the longest path from the head down to anyone, where leaving employee i costs informTime[i]: a DFS over the tree built from manager.

Why not another pattern? Walking up from every employee to the head is O(n · depth) without memoisation.

Approach:

1. Build reports[m] lists from the manager array.
2. DFS from the head carrying the time the news arrives.
3. The answer is the latest arrival time.

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        reports = [[] for _ in range(n)]
        for emp, boss in enumerate(manager):
            if boss != -1:
                reports[boss].append(emp)
        latest = 0
        stack = [(headID, 0)]  # (employee, minute the news reaches them)
        while stack:
            emp, t = stack.pop()
            latest = max(latest, t)
            for r in reports[emp]:
                stack.append((r, t + informTime[emp]))  # all direct reports hear it together
        return latest

What the code is doing, line by line:

1. The manager array lists parents; reversing it gives each manager's reports.
2. A report hears the news informTime[manager] minutes after its manager did.
3. Branches run in parallel, so the answer is the maximum arrival time, not the sum.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single employee → 0.
• A long chain of managers.
• A wide tree where only the head has informTime.

Complexity: O(n) time and space.

Problem: A tree of one-way roads; reverse the fewest roads so every city can reach city 0.

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 5 * 10⁴ · connections.length == n - 1 · connections[i].length == 2 · 0 ≤ ai, bi ≤ n - 1 · ai != bi

From brute force to the pattern: Testing whether each city can reach 0 and flipping by trial is quadratic or worse; one DFS is O(n).

Spot it: Treat roads as undirected for exploring, but remember their direction. In a DFS from 0, every edge used goes from a city nearer 0 to one further away; if the original road points that way (away from 0), it must be flipped.

Why not another pattern? Checking reachability to 0 from every city separately is O(n²).

Approach:

1. For each road a → b, add (b, 1) to a's list (original direction, would need flipping) and (a, 0) to b's list.
2. DFS from 0; when moving to an unvisited neighbour along a cost-1 entry, count a flip.

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        adj = [[] for _ in range(n)]
        for a, b in connections:
            adj[a].append((b, 1))  # road a -> b points away from a: flip if we walk a -> b
            adj[b].append((a, 0))  # walking b -> a goes against the road: already fine
        flips = 0
        seen = [False] * n
        seen[0] = True
        stack = [0]
        while stack:
            city = stack.pop()
            for nxt, away in adj[city]:
                if not seen[nxt]:
                    seen[nxt] = True
                    flips += away  # this road leads away from city 0
                    stack.append(nxt)
        return flips

What the code is doing, line by line:

1. Walking outward from 0, every road we travel should end up pointing back toward 0.
2. A road stored with flag 1 points in the walking direction (away from 0), so it must be reversed.
3. The network is a tree, so each road is walked exactly once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All roads already point toward 0 → 0.
• All roads point away from 0 → n − 1.
• A path-shaped network.

Complexity: O(n) time and space.

Problem: Method k and everything it reaches are suspicious. Remove them all if no other method invokes any of them; otherwise remove nothing. Return the remaining methods (any order).

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁵ · 0 ≤ k ≤ n - 1 · 0 ≤ invocations.length ≤ 2 * 10⁵ · invocations[i] == [ai, bi] · 0 ≤ ai, bi ≤ n - 1 · ai != bi · invocations[i] != invocations[j]

From brute force to the pattern: Running a search per suspicious method to find outside callers is O(n · e); one DFS and one edge scan is linear.

Spot it: "Everything reachable from k" is a DFS on the call graph. Then one pass over the edges checks for a call from outside into the set.

Why not another pattern? Checking each suspicious method's callers separately with fresh searches repeats work; one reachability pass plus one edge scan is enough.

Approach:

1. Build the call graph; DFS from k to mark suspicious.
2. For every invocation a → b: if a is not suspicious and b is, removal is impossible → return all methods.
3. Otherwise return the methods not marked.

class Solution:
    def remainingMethods(self, n: int, k: int, invocations: List[List[int]]) -> List[int]:
        calls = [[] for _ in range(n)]
        for a, b in invocations:
            calls[a].append(b)
        suspicious = [False] * n
        suspicious[k] = True
        stack = [k]
        while stack:
            m = stack.pop()
            for nxt in calls[m]:
                if not suspicious[nxt]:
                    suspicious[nxt] = True  # reached from k: suspicious too
                    stack.append(nxt)
        for a, b in invocations:
            if not suspicious[a] and suspicious[b]:
                return list(range(n))  # an outside method still needs it: remove nothing
        return [m for m in range(n) if not suspicious[m]]

What the code is doing, line by line:

1. DFS from k along invocation edges collects every method that k can reach.
2. An edge from outside into the set means a kept method would call a removed one, so nothing can be removed.
3. Edges from the set to outside are impossible (the outside node would have been reached), so only inbound edges need checking.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A cycle that includes k.
• No outside callers → remove all suspicious methods.
• k called by an outside method → return everything.

Complexity: O(n + e) time and space.

Problem: replacements maps single-letter keys to values that may contain placeholders %X%. Replace every placeholder in text until none remain (there are no cycles).

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ replacements.length ≤ 10 · Each replacements[i] is [key, value]; key is a single uppercase English letter · value is a non-empty string of at most 8 characters and may contain placeholders %<key>% · The replacements contain no cyclic dependencies · text consists of placeholders %<key>% separated by underscores

From brute force to the pattern: Replacing placeholders in the whole text over and over until stable repeats work. Memoised DFS expands each key once.

Spot it: Values depend on other keys, forming a DAG. The full expansion of a key is its value with each placeholder replaced by that key's full expansion: a DFS with memoisation (equivalently, a topological order).

Why not another pattern? Repeatedly replacing placeholders in the text until nothing changes can redo the same expansion many times.

Approach:

1. expand(key): scan its value; copy plain characters, and for %X% append expand(X). Memoise.
2. Apply the same scan to text.

from functools import lru_cache

class Solution:
    def applySubstitutions(self, replacements: List[List[str]], text: str) -> str:
        value = dict(replacements)

        def substitute(s):
            out = []
            i = 0
            while i < len(s):
                if s[i] == "%":
                    j = s.index("%", i + 1)  # closing percent sign
                    out.append(expand(s[i + 1:j]))  # replace %X% by X's full expansion
                    i = j + 1
                else:
                    out.append(s[i])
                    i = i + 1
            return "".join(out)

        @lru_cache(maxsize=None)
        def expand(key):
            return substitute(value[key])  # each key is expanded only once

        return substitute(text)

What the code is doing, line by line:

1. substitute walks a string and replaces each %X% placeholder by expand(X).
2. expand is memoised, so a key used many times is expanded once.
3. No cycles means the recursion always ends (keys only refer to keys further down the DAG).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A value with no placeholders.
• A key used several times.
• A chain of keys referring to each other (A → B → C).

Complexity: O(total output length) time and space (keys are expanded once each).

Problem: words is sorted in an alien alphabet. Return any letter order consistent with it, or "" if none exists (including a longer word placed before its own prefix).

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ words.length ≤ 100 · 1 ≤ words[i].length ≤ 100 · words[i] consists of only lowercase English letters

From brute force to the pattern: Trying all 26! letter orders is impossible. One edge per neighbouring pair plus a topological sort is linear.

Spot it: Each pair of neighbouring words reveals at most one rule: at their first differing position, a[i] comes before b[i]. Letters + rules form a directed graph; an order exists iff it's acyclic → topological sort.

Why not another pattern? Comparing every pair of words adds redundant edges (O(n²) pairs); neighbours alone carry all the information.

Approach:

1. Every letter that appears is a node with in-degree 0.
2. For each neighbouring pair, find the first differing letter and add edge a[i] → b[i]. If no difference and a is longer, return "".
3. Kahn's algorithm: repeatedly output a letter with in-degree 0 and lower its successors' in-degrees.
4. If not every letter was output, there's a cycle → "".

from collections import deque

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = {ch: set() for w in words for ch in w}  # every letter is a node
        indegree = {ch: 0 for ch in graph}
        for a, b in zip(words, words[1:]):  # neighbouring words
            for x, y in zip(a, b):
                if x != y:
                    if y not in graph[x]:
                        graph[x].add(y)  # x comes before y
                        indegree[y] += 1
                    break
            else:
                if len(a) > len(b):
                    return ""  # "abc" before "ab" is impossible
        queue = deque(ch for ch in indegree if indegree[ch] == 0)
        order = []
        while queue:
            ch = queue.popleft()
            order.append(ch)  # nothing left must come before ch
            for nxt in graph[ch]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)
        return "".join(order) if len(order) == len(graph) else ""  # missing letters = a cycle

What the code is doing, line by line:

1. Only the first difference between two sorted words tells anything; later letters are unconstrained.
2. The for … else runs when one word is a prefix of the other: fine if the shorter comes first, invalid otherwise.
3. The duplicate-edge check keeps in-degrees correct when the same rule appears twice.
4. Kahn's algorithm outputs letters whose predecessors are all placed; a cycle leaves some letters stuck.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A word followed by its own prefix → "".
• A cycle (z, x, z) → "".
• Letters with no rules (place them anywhere).

Complexity: O(C) time where C is the total length of all words; O(1) extra beyond that (at most 26 letters).

Problem: Return the k-th number of 1..n in lexicographical order (n up to 10⁹).

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ n ≤ 10⁹

From brute force to the pattern: Listing numbers in lexicographic order until the k-th is O(k) (up to 10⁹). Counting whole subtrees skips them in O(log n).

Spot it: Same prefix tree as Lexicographical Numbers, but too big to walk. Count how many numbers ≤ n start with prefix (sum the ranges [prefix·10^d, (prefix+1)·10^d) clipped to n). If k is beyond them, skip to prefix + 1; otherwise descend to prefix · 10.

Why not another pattern? Generating the order (LeetCode 386) is O(n) = 10⁹ steps.

Approach:

1. cur = 1, k −= 1 (cur itself is the first number).
2. steps = how many numbers ≤ n have prefix cur.
3. If steps ≤ k: skip the subtree: k −= steps, cur += 1.
4. Else: descend: k −= 1, cur *= 10. Stop when k == 0.

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def count_with_prefix(prefix):
            total = 0
            first = prefix
            last = prefix  # the range of numbers with this prefix at the current length
            while first <= n:
                total += min(last, n) - first + 1
                first = first * 10  # one digit longer
                last = last * 10 + 9
            return total

        cur = 1
        k = k - 1  # cur = 1 is already the 1st number
        while k > 0:
            steps = count_with_prefix(cur)
            if steps <= k:
                k = k - steps  # the answer isn't under cur: skip the whole subtree
                cur = cur + 1
            else:
                k = k - 1  # it is under cur: step into the first child
                cur = cur * 10
        return cur

What the code is doing, line by line:

1. For prefix 1 and n = 13: lengths 1 → [1, 1], length 2 → [10, 13]; total 5 numbers.
2. If the remaining k is at least the subtree size, the answer lies to the right: skip to the next sibling.
3. Otherwise the answer is inside: moving to the first child cur · 10 passes over cur itself, using one step.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 → 1.
• n = 1.
• n a power of 10 (the last subtree is partial).

Complexity: O(log² n) time (≤ 10 levels × ≤ 10 siblings per level × O(log n) counting), O(1) space.

Problem: Count paths in a tree whose two ends have the same value and no node on the path has a larger value. A single node counts.

Solve it on LeetCode ↗

Constraints: n == vals.length · 1 ≤ n ≤ 3 * 10⁴ · 0 ≤ vals[i] ≤ 10⁵ · edges.length == n - 1 · edges[i].length == 2 · 0 ≤ ai, bi < n · ai != bi · edges represents a valid tree.

From brute force to the pattern: Searching from every node with a path-maximum check is O(n²). Sorting + union-find counts all pairs in O(n log n).

Spot it: Process values from small to large and connect nodes only through edges whose both ends are ≤ the current value. Inside one connected piece, any two nodes with the current (maximum) value form a good path. Union-find builds the pieces incrementally.

Why not another pattern? DFS from every node, tracking the path maximum, is O(n²).

Approach:

1. Sort edges by max(vals[a], vals[b]); group nodes by value.
2. For each value v in increasing order: union every edge whose larger end is v.
3. Count nodes with value v per component root: c such nodes give c · (c − 1) / 2 paths.
4. Add n for the single-node paths.

from collections import Counter, defaultdict

class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        n = len(vals)
        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]  # path halving
                x = parent[x]
            return x

        by_value = defaultdict(list)
        for i, v in enumerate(vals):
            by_value[v].append(i)
        edges = sorted(edges, key=lambda e: max(vals[e[0]], vals[e[1]]))
        good = n  # every single node is a good path
        e = 0
        for v in sorted(by_value):
            while e < len(edges) and max(vals[edges[e][0]], vals[edges[e][1]]) == v:
                a, b = edges[e]
                parent[find(a)] = find(b)  # both ends are <= v: join their components
                e = e + 1
            groups = Counter(find(i) for i in by_value[v])  # nodes of value v per component
            for c in groups.values():
                good += c * (c - 1) // 2  # every pair of them is a good path
        return good

What the code is doing, line by line:

1. When value v is processed, components contain only nodes with values ≤ v, so v is the maximum on any path inside them.
2. Two nodes of value v in the same component are joined by a path whose maximum is v: a good path.
3. Edges are added once their larger endpoint's value is reached, so smaller values are already connected.
4. c · (c − 1) / 2 counts unordered pairs; single nodes are counted once up front.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single node → 1.
• All values equal → n(n + 1)/2.
• A bigger value between two equal ones blocks the path.

Complexity: O(n log n) time (sorting + near-constant union-find), O(n) space.

Problem: Connect one node of tree 1 with one node of tree 2 by a new edge. Return the minimum possible diameter of the merged tree.

Solve it on LeetCode ↗

Constraints: 1 ≤ n, m ≤ 10⁵ · edges1.length == n - 1 · edges2.length == m - 1 · edges1[i].length == edges2[i].length == 2 · edges1[i] = [ai, bi] · 0 ≤ ai, bi < n · edges2[i] = [ui, vi] · 0 ≤ ui, vi < m · The input is generated such that edges1 and edges2 represent valid trees.

From brute force to the pattern: Trying all n · m connections and recomputing the diameter is far too slow. Two diameters and a formula are linear.

Spot it: The new longest path either stays inside one tree (d1 or d2) or crosses the new edge. Crossing is shortest when both ends are tree centres, whose farthest distance is ⌈d/2⌉. Each diameter comes from two DFS/BFS passes (farthest node from anywhere, then farthest from it).

Why not another pattern? Trying every pair of nodes to connect is O(n · m) pairs, each needing a diameter computation.

Approach:

1. Diameter of a tree: from node 0 find the farthest node a; from a the farthest distance is the diameter.
2. Compute d1, d2.
3. Return max(d1, d2, (d1 + 1) // 2 + (d2 + 1) // 2 + 1).

class Solution:
    def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
        def diameter(edges):
            n = len(edges) + 1
            adj = [[] for _ in range(n)]
            for a, b in edges:
                adj[a].append(b)
                adj[b].append(a)

            def farthest(src):
                dist = [-1] * n
                dist[src] = 0
                stack = [src]
                while stack:
                    u = stack.pop()
                    for v in adj[u]:
                        if dist[v] < 0:
                            dist[v] = dist[u] + 1  # tree: one path to each node
                            stack.append(v)
                far = max(range(n), key=lambda i: dist[i])
                return far, dist[far]

            end, _ = farthest(0)  # one end of a longest path
            _, d = farthest(end)  # its farthest node is the other end
            return d

        d1 = diameter(edges1)
        d2 = diameter(edges2)
        through_edge = (d1 + 1) // 2 + (d2 + 1) // 2 + 1  # centre to centre, plus the new edge
        return max(d1, d2, through_edge)

What the code is doing, line by line:

1. In a tree, the farthest node from any start is an end of some diameter; the farthest node from that end gives the diameter.
2. A tree's centre is at distance ⌈d/2⌉ from every node at worst, and no node does better.
3. A path through the new edge has length (reach in tree 1) + 1 + (reach in tree 2), minimised by joining the centres.
4. The old diameters can still be longer than that, hence the max.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A tree with one node (edges empty → diameter 0).
• One tree's diameter dominates.
• Odd vs even diameters (the ceiling).

Complexity: O(n + m) time and space.

Problem: Each integer in a nested list is weighted by its depth (top level = 1). Return the weighted sum.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ nestedList.length ≤ 50 · The values of the integers in the nested list is in the range [-100, 100] · The maximum depth of any integer is less than or equal to 50

From brute force to the pattern: This DFS is already linear; a BFS by levels works equally well.

Spot it: The nesting is a tree: lists are internal nodes, integers are leaves. DFS with the current depth adds each leaf's contribution.

Why not another pattern? Flattening first loses the depth information.

Approach:

1. dfs(items, depth): for each item, an integer adds value · depth; a list adds dfs(list, depth + 1).
2. Start with dfs(nestedList, 1).

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(items, depth):
            total = 0
            for item in items:
                if item.isInteger():
                    total += item.getInteger() * depth  # leaf: weighted by how deep it is
                else:
                    total += dfs(item.getList(), depth + 1)  # go one level deeper
            return total

        return dfs(nestedList, 1)

What the code is doing, line by line:

1. NestedInteger is LeetCode's interface: isInteger(), getInteger(), getList().
2. Each integer is visited once, at its own depth.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Empty inner lists.
• Deep nesting.
• Negative numbers.

Complexity: O(N) time for N integers and lists, O(D) space for depth D.

Problem: Can the nodes be split into two sets so every edge goes between the sets?

Solve it on LeetCode ↗

Constraints: graph.length == n · 1 ≤ n ≤ 100 · 0 ≤ graph[u].length < n · 0 ≤ graph[u][i] ≤ n - 1 · graph[u] does not contain u. · All the values of graph[u] are unique. · If graph[u] contains v, then graph[v] contains u.

From brute force to the pattern: Every split: O(2ⁿ); colouring: O(V + E).

Spot it: Graph colouring with DFS (or BFS): give a node colour 0, its neighbours colour 1, and so on. A conflict means an odd cycle.

Why not another pattern? Trying all 2ⁿ splits is exponential.

Approach:

1. For each uncoloured node, start a DFS with colour 0.
2. Neighbours get the opposite colour; an already-coloured neighbour with the same colour → false.

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = [-1] * len(graph)
        for s in range(len(graph)):
            if color[s] != -1:
                continue
            color[s] = 0
            stack = [s]
            while stack:
                u = stack.pop()
                for v in graph[u]:
                    if color[v] == -1:
                        color[v] = 1 - color[u]  # opposite side
                        stack.append(v)
                    elif color[v] == color[u]:
                        return False  # an edge inside one side
        return True

What the code is doing, line by line:

1. The graph may be disconnected, so every component is coloured.
2. Within a component the colouring is forced, so one conflict proves it's not bipartite.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Disconnected graph.
• Odd cycle → false.
• Isolated nodes.

Complexity: O(V + E) time, O(V) space.

Problem: Split people 1..n into two groups so no pair that dislikes each other ends up together.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 2000 · 0 ≤ dislikes.length ≤ 10⁴ · dislikes[i].length == 2 · 1 ≤ ai < bi ≤ n · All the pairs of dislikes are unique.

From brute force to the pattern: All 2ⁿ splits vs a linear colouring.

Spot it: Same as Is Graph Bipartite?: build an adjacency list from dislikes and two-colour it with DFS.

Why not another pattern? Trying all splits is exponential.

Approach:

1. Build the undirected graph.
2. Colour each component; a same-colour edge means impossible.

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        adj = [[] for _ in range(n + 1)]
        for a, b in dislikes:
            adj[a].append(b)
            adj[b].append(a)
        group = [0] * (n + 1)  # 0 = unassigned, 1 / -1 = the two groups
        for s in range(1, n + 1):
            if group[s]:
                continue
            group[s] = 1
            stack = [s]
            while stack:
                u = stack.pop()
                for v in adj[u]:
                    if group[v] == 0:
                        group[v] = -group[u]  # must be in the other group
                        stack.append(v)
                    elif group[v] == group[u]:
                        return False
        return True

What the code is doing, line by line:

1. Each dislike pair must be split, which is exactly an edge in a bipartite graph.
2. People with no dislikes can go anywhere.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No dislikes → true.
• Triangle of dislikes → false.
• Several components.

Complexity: O(n + e) time and space.

Problem: Recipes need ingredients, which may be supplies or other recipes. Return every recipe that can be made (any order).

Solve it on LeetCode ↗

Constraints: n == recipes.length == ingredients.length · 1 ≤ n ≤ 100 · 1 ≤ ingredients[i].length, supplies.length ≤ 100 · 1 ≤ recipes[i].length, ingredients[i][j].length, supplies[k].length ≤ 10 · recipes[i], ingredients[i][j], and supplies[k] consist only of lowercase English letters. · All the values of recipes and supplies combined are unique. · Each ingredients[i] does not contain any duplicate values.

From brute force to the pattern: Repeated full scans until no change is O(r · total); topological sort is linear.

Spot it: Ingredients → recipe edges form a dependency graph; start from the supplies and unlock recipes whose ingredients are all available: Kahn's topological sort with per-recipe counters. Recipes in a cycle never unlock.

Why not another pattern? Repeatedly scanning all recipes until nothing changes is O(r²).

Approach:

1. need[r] = number of ingredients of r; users[ing] = recipes using ing.
2. Queue all supplies; popping an item decrements need of its users.
3. A recipe reaching 0 is made: record and queue it.

from collections import defaultdict, deque

class Solution:
    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:
        need = {}
        users = defaultdict(list)  # ingredient -> recipes that use it
        for recipe, ings in zip(recipes, ingredients):
            need[recipe] = len(ings)
            for ing in ings:
                users[ing].append(recipe)
        queue = deque(supplies)
        made = []
        while queue:
            item = queue.popleft()
            for recipe in users[item]:
                need[recipe] -= 1
                if need[recipe] == 0:
                    made.append(recipe)  # everything it needs is available
                    queue.append(recipe)  # it can now be an ingredient
        return made

What the code is doing, line by line:

1. Each available item lowers the missing-ingredient count of the recipes that use it.
2. Recipes in a dependency cycle (or needing missing supplies) never reach 0.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Cyclic recipes.
• A recipe that needs another recipe.
• Missing supplies.

Complexity: O(r + total ingredients + s) time and space.

Problem: Every city sends one representative to city 0 by car (cars have seats seats; people can share). Return the minimum litres (1 per road per car).

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁵ · roads.length == n - 1 · roads[i].length == 2 · 0 ≤ ai, bi < n · ai != bi · roads represents a valid tree. · 1 ≤ seats ≤ 10⁵

From brute force to the pattern: Simulating the drive is complex; per-edge counting is O(n).

Spot it: Everyone in a subtree must cross the road to its parent, and they can pool into ceil(size / seats) cars. Subtree sizes come from a DFS from the capital.

Why not another pattern? Simulating cars driving and merging is complicated; counting per edge is direct.

Approach:

1. DFS from 0 computing subtree sizes (iteratively).
2. For every non-root city: add ceil(size / seats).

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        n = len(roads) + 1
        adj = [[] for _ in range(n)]
        for a, b in roads:
            adj[a].append(b)
            adj[b].append(a)
        parent = [-1] * n
        order = [0]
        for u in order:  # BFS order from the capital
            for v in adj[u]:
                if v != parent[u]:
                    parent[v] = u
                    order.append(v)
        size = [1] * n
        fuel = 0
        for u in reversed(order[1:]):  # children before parents
            fuel += -(-size[u] // seats)  # cars needed on the road from u to its parent
            size[parent[u]] += size[u]
        return fuel

What the code is doing, line by line:

1. People from a subtree only ever travel up toward the capital, so they all cross the edge above it.
2. Merging into as few cars as possible on each edge is achievable simultaneously for all edges.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Only the capital → 0.
• seats = 1.
• A star around the capital.

Complexity: O(n) time and space.

Problem: Courses have durations and prerequisites; any number run in parallel. Return the minimum months to finish all.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 5 * 10⁴ · 0 ≤ relations.length ≤ min(n * (n - 1) / 2, 5 * 10⁴) · relations[j].length == 2 · 1 ≤ prevCoursej, nextCoursej ≤ n · prevCoursej != nextCoursej · All the pairs [prevCoursej, nextCoursej] are unique. · time.length == n · 1 ≤ time[i] ≤ 10⁴ · The given graph is a directed acyclic graph.

From brute force to the pattern: Month-by-month simulation is slow; topological DP is linear.

Spot it: A course can start once all prerequisites finish, so its finish time is its duration plus the latest prerequisite finish: a longest path in a DAG, computed in topological order (Kahn's algorithm).

Why not another pattern? Simulating month by month is O(total time); DFS without memo repeats work.

Approach:

1. Build the graph and in-degrees.
2. Start with courses that have no prerequisites: finish = time.
3. Pop in topological order; for each next course: start[next] = max(start[next], finish[u]).
4. Answer: the maximum finish.

from collections import deque

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        nxt = [[] for _ in range(n)]
        indeg = [0] * n
        for a, b in relations:
            nxt[a - 1].append(b - 1)
            indeg[b - 1] += 1
        start = [0] * n  # earliest start = latest prerequisite finish
        queue = deque(i for i in range(n) if indeg[i] == 0)
        finish = [0] * n
        while queue:
            u = queue.popleft()
            finish[u] = start[u] + time[u]
            for v in nxt[u]:
                start[v] = max(start[v], finish[u])  # v must wait for u
                indeg[v] -= 1
                if indeg[v] == 0:
                    queue.append(v)
        return max(finish)

What the code is doing, line by line:

1. Kahn's algorithm processes a course only after all its prerequisites, so start[v] is final when v is popped.
2. Parallelism means only the slowest prerequisite chain matters.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No relations → max(time).
• A long chain.
• Several prerequisites with different finish times.

Complexity: O(n + e) time and space.

Problem: From any start, you collect coins within distance 2 and walk edges; return the fewest edges walked to collect all coins and return to the start.

Solve it on LeetCode ↗

Constraints: n == coins.length · 1 ≤ n ≤ 3 * 10⁴ · 0 ≤ coins[i] ≤ 1 · edges.length == n - 1 · edges[i].length == 2 · 0 ≤ ai, bi < n · ai != bi · edges represents a valid tree.

From brute force to the pattern: Simulating from every start vertex is O(n²); pruning leaves is O(n).

Spot it: Branches without coins are never worth entering: peel leaves without coins repeatedly (Kahn-style topological pruning on degrees). Then coins at distance ≤ 2 are collected from afar, so peel two more layers of leaves. Every remaining edge is walked exactly twice.

Why not another pattern? Trying every start vertex with a search is O(n²).

Approach:

1. Degrees; queue all leaves without coins and delete them repeatedly (a parent may become a coin-less leaf).
2. Then remove the current leaves twice (two rounds, not repeatedly).
3. Answer: 2 · max(0, remaining nodes − 1).

from collections import deque

class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
        n = len(coins)
        adj = [set() for _ in range(n)]
        for a, b in edges:
            adj[a].add(b)
            adj[b].add(a)
        alive = n
        queue = deque(i for i in range(n) if len(adj[i]) == 1 and not coins[i])
        while queue:  # 1) prune branches with no coins
            u = queue.popleft()
            if len(adj[u]) != 1:
                continue
            v = adj[u].pop()
            adj[v].discard(u)
            alive -= 1
            if len(adj[v]) == 1 and not coins[v]:
                queue.append(v)
        for _ in range(2):  # 2) coins within distance 2 are reachable from the parent's parent
            leaves = [i for i in range(n) if len(adj[i]) == 1]
            for u in leaves:
                if adj[u]:
                    v = adj[u].pop()
                    adj[v].discard(u)
                    alive -= 1
        return 2 * max(0, alive - 1)  # walk every remaining edge there and back

What the code is doing, line by line:

1. After pruning, every leaf has a coin; standing two steps inside collects it, so two leaf layers never need to be visited.
2. The remaining nodes form a tree whose every edge must be walked out and back.
3. If at most one node remains, no walking is needed.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No coins → 0.
• All coins within distance 2 of one node → 0.
• A long path with coins at both ends.

Complexity: O(n) time and space.

Problem: In a directed tree, for every node, return how many edges must be reversed so that it can reach every other node.

Solve it on LeetCode ↗

Constraints: 2 ≤ n ≤ 10⁵ · edges.length == n - 1 · edges[i].length == 2 · 0 ≤ ui == edges[i][0] < n · 0 ≤ vi == edges[i][1] < n · ui != vi · The input is generated such that if the edges were bi-directional, the graph would be a tree.

From brute force to the pattern: A traversal from every node is O(n²); rerooting is O(n).

Spot it: From root r, every edge must point away from r. Count the edges pointing toward node 0 with one DFS; then reroot: moving from p to child c, only the edge between them changes its role (+1 if it pointed p → c, −1 if c → p).

Why not another pattern? A separate DFS from every node is O(n²).

Approach:

1. Store each edge both ways with a flag: (v, 0) if it points u → v (fine from u), (u, 1) on v's side (needs reversal when walked from v).
2. DFS from 0 summing the flags: ans[0].
3. Second pass in DFS order: ans[child] = ans[parent] + (1 if the edge points parent → child else −1).

class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append((v, 0))  # walking u -> v follows the edge
            adj[v].append((u, 1))  # walking v -> u needs a reversal
        parent = [-1] * n
        order = [0]
        root_cost = 0
        seen = [False] * n
        seen[0] = True
        for u in order:  # BFS order from node 0
            for v, rev in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    parent[v] = u
                    root_cost += rev  # edges pointing toward node 0
                    order.append(v)
        answer = [0] * n
        answer[0] = root_cost
        for u in order:
            for v, rev in adj[u]:
                if parent[v] == u:
                    answer[v] = answer[u] + (1 if rev == 0 else -1)  # only edge (u, v) changes direction need
        return answer

What the code is doing, line by line:

1. From root 0, an edge needs reversing exactly when it points toward the root.
2. Moving the root from u to its child v flips the requirement for the edge between them and nothing else.
3. If that edge pointed u → v, it was fine for u but needs reversing for v (+1); otherwise −1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A path pointing one way.
• A star with mixed directions.
• n = 2.

Complexity: O(n) time and space.

Problem: n courses with prerequisite pairs [prev, next]; take any number of available courses per semester. Return the minimum semesters, or −1 if impossible.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ n ≤ 5000 · 1 ≤ relations.length ≤ 5000 · relations[i].length == 2 · 1 ≤ prevCourse_i, nextCourse_i ≤ n · prevCourse_i != nextCourse_i · All the pairs [prevCourse_i, nextCourse_i] are unique.

From brute force to the pattern: Rescanning all courses each semester is O(n²); layered Kahn's is O(n + E).

Spot it: Prerequisites form a directed graph → topological sort. Taking every available course each semester is optimal, so process Kahn's queue level by level: the number of levels is the answer, and if not every course is taken there is a cycle.

Why not another pattern? Simulating semesters by rescanning all courses is O(n²); plain DFS finds an order, not the number of layers.

Approach:

1. Build the graph and in-degrees.
2. Queue all courses with in-degree 0.
3. Each semester: take the whole queue, lower neighbours' in-degrees, queue the new zeros.
4. Return semesters if all n were taken, else −1.

from collections import deque

class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        graph = [[] for _ in range(n + 1)]
        indegree = [0] * (n + 1)
        for prev, nxt in relations:
            graph[prev].append(nxt)
            indegree[nxt] += 1
        queue = deque(c for c in range(1, n + 1) if indegree[c] == 0)  # courses with no prerequisites
        semesters = taken = 0
        while queue:
            semesters += 1
            for _ in range(len(queue)):  # everything available this semester
                course = queue.popleft()
                taken += 1
                for nxt in graph[course]:
                    indegree[nxt] -= 1
                    if indegree[nxt] == 0:
                        queue.append(nxt)
        return semesters if taken == n else -1  # untaken courses sit on a cycle

What the code is doing, line by line:

1. A course becomes available the semester after its last prerequisite; taking everything available never hurts.
2. So the answer is the length of the longest prerequisite chain, which is the number of BFS levels.
3. Courses on a cycle never reach in-degree 0, so taken < n signals −1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A cycle → −1.
• No relations between some courses (all in semester 1).
• One long chain → n semesters.

Complexity: O(n + E) time and space.