- To keep track of intermediate result along a path, record a var together with the node that get pushed to stack / queue. Example: queue = [(node value, current result along path)]
- During graph search, can override calculated result to make graph simpler for next search iteration Example: https://github.com/memoryonrepeat/brainteasers/blob/master/leetcode/numberofislands.py
To practice:
- Find largest k elements (in terms of value etc...) in a collection. What to do when facing this pattern ?
- Inspired by computational geometry. Ideal for problems involving segments / intervals
- Can be multi-dimensional
- Steps:
- Sort critical points
- Sweep through the sorted points, keep track of current item / critical stats and upate them if needed
- Extract answer from info got while sweeping
Reverse BFS/DFS: From destinations, search backwards to find origins. Suitable for problems asking for distance to nearest milestones https://leetcode.com/problems/walls-and-gates/
Binary lifting technique for solving LCA-related problems
def dfs(node, state):
if state is a solution:
report(state) # e.g. add state to final result list
return
for child in children:
if child is a part of a potential solution:
state.add(child) # make move
dfs(child, state)
state.remove(child) # backtrack
Can also pass updated candidate as parameter to avoid adding / removing manually - less mental overhead
def dfs(node, state):
if state is a solution:
report(state) # e.g. add state to final result list
return
for child in children:
if child is a part of a potential solution:
dfs(child, state + [child])
- Consider dp(i) = solution from starting point until i. Then expand solution to i++, or starting from biggest i then reduce to i--. Basically make sure that intermediate results are calculated during traversal. Example: Max area of islands, maximal rectangle , longest increasing path, edit distance. Read more: https://labuladong.gitbook.io/algo-en/i.-dynamic-programming/optimalsubstructure.
- How to come up with this: Since DP problems are based on solving optimal overlapping subproblems, it would be intuitive to think of what kind of past subproblems would have been solved as we progress / move forward the data structure. For example in string, we want to focus on the past substrings as we scan through the end. In matrix / 2D array, we also want to consider the submatrices as we move from one end to the others. So basically "look back at our footprints" and try to derive something from it. This philosophy is the essence of many DP solutions.
On recursive call, can try returning a tuple containing all useful information for parent call, not just a value. Example: https://leetcode.com/problems/longest-univalue-path/
When backtracking, see if it's possible to apply an order onto candidate selection (either sort or simply go from left to right etc...) to reduce duplicates and make sure there is no overlapping in the search space.
General approach for stock buying/selling problems using multi-dimensional DP
- Recently noted that most data structures were born to optimize a specific kind of query
- Example: Priority queue / heap is meant to query the max item or one with highest degree of something. Stack is meant to keep track of insertion order. Monotonic stack is also meant for max / min item querying. Union find is to check if two elements belong to same component etc...
- Can also combine multiple data structures to optimize some kind of query. For example to find mean of data stream, can keep one max heap and one min heap for two parts of the input and get mean from the intersection of those - LC 295
- Therefore, when solving a problem, can think of what kind of query is this trying to answer, then derive a data structure optimized for that query.