Leetcode Notes

797. All Paths From Source to Target

Use recursion to find all possible paths from the source node to the destination node.
A few important things to think about when writing recursion algorithms:

• How to define the recursion function: what to accept as input, what to return (maybe no return value, but instead modifying global variables at each recursion)?
• The scope of each recursion: what's the responsibility at each recursion? For example, do we append the child nodes at this recursion, or leave it to the next recursion? i.e. only append the current node at this recursion, or only append the child nodes? Note that this will affect how we define base case as well.
• The base case/end of recursion: sometimes the base case is implicitly executed when looking at the next step in the current recusion.

200. Number of Islands

Combine 2D array traversal + BFS to determine the number of isolated graphs.

• When approaching a problem, don't restrict yourself to only one algorithm. Like in this case, it's a combination of array traversal and BFS.
• Try to think without specific algorithm technique first, but to first come up with a high level strategy, to make some observations, then think of the specific realisation of it.

695. Max Area of Island

Very similar to the problem above.

Again, one crucial thing when doing recursion is to be very clear about what each recursion does. In this example, there's 2 alternatives:

1. Add the area of child nodes each recursion
2. Add the area of the current node

151. Reverse Words in a String

The take away message is to utilise the idea of "global reverse" + "partial reverse", which is useful for many in-place string manipulation problems.

Greedy

• The idea is "each step we will not miss the global optimal solution"
• Validity often supported by "proof by contradiction"
• When to use? It's by intuition and trials and errors really...

134. Gas Station

-- make close observations when planning each greedy step.

A typical greedy solution would use 2 pointer method: both start from index 0, curr goes clockwise while base goes anti-clockwise. Whenever the currentSum is < 0, meaning out of gas, we move base anti-clockwise by 1 index. The loop terminates when the 2 pointers intersect (together complete a whole circle)

The key observation here is, whenever the currSum between i and i + n is negative, any base starting between [i, i + n] would also result in negative currSum, but position i - 1 might give us extra gas so it's worth trying; so instead of moving base forward, we need to move it backward.

53. Maximum Subarray

Greedy is harder than DP for this problem.

Again, the key here is to make close observation, then use two-pointer strategy and increment each pointer correctly.

55. Jump Game

From each position i we have nums[i] many ways to jump, which seems to result in too many possibilities at the first glance. However, the observation is that no matter how many ways we could reach position i, what we can reach from this position onwards is the same.

Therefore, multiple jump capacities provided at different positions will always flatten to one single jump capacity. In other words, each following position will always overwrite the current jump capacity, so we only need to keep track of how far we can jump at each position, starting from i = 0

Another way of thinking is to start from the back and travel backwards, we look for the first position x that can jump to the last element (i.e. nums[x] >= distance from x to the last element), then update this position as our destination (since if we could reach x, we could reach the last element), look for position that can reach x, so on and so forth until we travel back to the first element.

Dynamic Programming

• Find out the sub-problems: dp[i] (sometimes it could be multi-dimensional)
• Find out the next-step-logic: dp[i + 1] = ?
• Find out the base cases to start with: dp[0], dp[1], etc

1049. Last Stone Weight II

-- Use mathmatical model to simplifiy the problem

At first, the problem of recursively pairing the stones and getting resultant stones to pair again seems complicated, but after putting it into an equation everything gets very clear:

1. say the array is [a,b,c,d,e]
2. say we smash them this way result = (a-b)-c-(d-e)
3. rearrange the equation we get result = (a+e)-(b+c+d)

Therefore, the observation is that ultimately we just want to find a subset of the array such that sum(subset_array) is closest to sum(original_array) / 2

The power of mathmatical modelling can be seen in other problems such as:

• 15. 3Sum
• 454. 4Sum II