main idea: for nth tx,ty, ( assuming tx > ty), the nth tx comes from the (n-1)th tx + the (n-1)th ty ==> in order to make ty, tx increase, there has to be a difference between these two number for any sx > tx or sy > ty, there...
[Read More]
1163. Last Substring in Lexicographical Order
Duval algorithm time O(N) space O(1)
```python
[Read More]
42. Trapping Rain Water
class Solution: def trap(self, height: List[int]) -> int: """ main idea: two pointers. l, r move toward each other. get current l_max and r_max; then based on case, 1: l_max < r_max 2: r_max < l_max to get water at pos left/ right """ # time O(N) space O(1) if...
[Read More]
33. Search in Rotated Sorted Array
```python “”” 1. mid point is pivot point 2. mid ptr is between ascending sorted arr ==> how to find lo/hi?? => compare mid ptr with most left and most right [l, mid) and (mid,r]; That says, mid ptr is switching roles as left ptr and right ptr between corresponding...
[Read More]
236. Lowest Common Ancestor of a Binary Tree
```python time O(N) space O(H) H: stack Definition for a binary tree node. class TreeNode: def init(self, x): self.val = x self.left = None self.right = None time O(N) space O(N) class Solution: def lowestCommonAncestor(self, root: ‘TreeNode’, p: ‘TreeNode’, q: ‘TreeNode’) -> ‘TreeNode’: “”” tc O(N) sc O(H) main idea:...
[Read More]