Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
This is a classic backtracking problem. Each digit corresponds to a set of characters (phone keypad mapping). We explore all possible combinations by building strings recursively.
We build a tree where each node contains up to 26 children (for each lowercase letter). Each node also keeps a boolean flag isEnd to mark the end of a word.
There are numCourses courses labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that to take course a you must first take course b.
Return true if you can finish all courses. Otherwise, return false.
This is essentially asking whether the directed graph has a cycle. If there is no cycle, a topological ordering exists and you can finish all courses.
💬 Examples
Example 1
1 2 3
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: Take course 0 first, then course 1.
Example 2
1 2 3
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: 0 depends on 1 and 1 depends on 0 → cycle.
while (!q.isEmpty()) { intsize= q.size(); minutes++; for (ints=0; s < size; s++) { int[] cur = q.poll(); for (int[] d : dirs) { intx= cur[0] + d[0], y = cur[1] + d[1]; if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1) continue; grid[x][y] = 2; fresh--; q.offer(newint[]{x, y}); } } }
return fresh == 0 ? minutes : -1; } }
⏱ Time and Space Complexity
Time Complexity: O(m × n), each cell is visited at most once.
Space Complexity: O(m × n) for the BFS queue.
✍️ Summary
Treat all rotten oranges as starting points.
Run BFS layer by layer to simulate time passing.
Return minutes when all fresh oranges are rotten, otherwise -1.
Given the root of a binary tree, return the maximum path sum of the tree.
A path is any sequence of nodes where each pair of adjacent nodes has an edge connecting them. A path does not need to pass through the root and cannot revisit a node. The path sum is the sum of node values along the path.
💬 Examples
Example 1
1 2 3
Input: root = [1,2,3] Output: 6 Explanation: The maximum path is 2 → 1 → 3.
Example 2
1 2 3
Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The maximum path is 15 → 20 → 7.
💡 Intuition
At each node, there are two different concepts:
Max Gain to Parent (what we can return upward): max(node.val, node.val + leftGain, node.val + rightGain)
This represents the best one-side path that can be extended by the parent.
Max Path Through Node (candidate for global answer): node.val + max(0, leftGain) + max(0, rightGain)
When a path goes through the current node and uses both sides (if beneficial).
Negative gains should be treated as 0 (i.e., discard them).
We do a postorder DFS to compute gains bottom-up while maintaining a global maximum.
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q.
The lowest common ancestor is defined between two nodes p and q as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).
💬 Example
Example 1
1 2 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.
Example 2
1 2 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself.
💡 Approach: Recursive DFS
We traverse the binary tree recursively:
If the current node is null, return null.
If the current node matches p or q, return it.
Recursively search left and right subtrees.
If both left and right return non-null, the current node is the LCA.
Otherwise, return the non-null child.
🔢 Java Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution {{ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {{ if (root == null || root == p || root == q) {{ return root; }}