Diameter of Binary Tree
543. Diameter of Binary Tree
Solution
The same as 1 + left tree’s height + right tree’s height
Keep a variable to track the current longest path
As we checking each node’s height, the variable will get updated and store the maximum value in the end.
```python
def diameterOfBinaryTree(self, root):
“””
:type root: TreeNode
:rtype: int
“...
Best Time to Buy and Sell Stock
121. Best Time to Buy and Sell Stock
Solution 1 - DP
Keep the seen minimum buy price and check if sell at current price can get more profit.
We do not get the minimum value for the whole list first because we can only sell after buy.
So [2, 4, 5, 1], when we are at 5 we can only get 3 because 2 is the minimum price up to now.
...
Merge Two Sorted Lists
21. Merge Two Sorted Lists
Solution
Keep 3 pointer, 1 for l1, 1 for l2 and 1 for the merged list.
When l1 or l2 has reached to the end, link the other one directly to the merged list, without copying the value.
def mergeTwoLists(self, l1, l2):
while l1 is not None and l2 is not None:
if l1.val < l2.val:
tm...
Find All Numbers Disappeared in an Array
448. Find All Numbers Disappeared in an Array
Solution
Since the array contians number in range [1, n], we can use their value as index to track the information.
When a number is visited, we mark the value it is point to negative.
The positive number’s index disappeared in the array.
Reference
def findDisappeared...
Single Number
136. Single Number
Solution 1
Use set to track all seen appeared numbers.
Remove seen number if it is re-visited.
The last one is the single number.
Space Complexity: O(n)
Solution 2 - Bitwise XOR
0 ^ N = N and N ^ N = 0
So XOR all number together, only the single number’s value is preserved.
...
Move Zeroes
448. Move Zeroes
Solution 1 - Swap
If the num is not 0, move forward if possible, i.e. zero < i, nums[zero] = nums[i]
If the num is 0, leave it and search for the number to ‘fill in’ it.
The key point is zero < i because zero is not updated at each iteration.
def moveZeroes(self, nums):
"""
:type nu...
Majority Element
169. Majority Element
Solution 1
The majority must be at index n/2 after sorting, i.e. medium number
Word Break
139. Word Break
Solution
Check if the word can be broke up to an index i.
For any substring end at i, we check if there exists any breakable word end at j can be combined with a word in
wordDict to form it.
j < i because of DP.
j > i - max_len because the prefix word needs to be long enough.
```python
def wordBreak(self, s...
199 post articles, 25 pages.