Algorithmic Thinking

Strategy
- Talk loud
- Always say and actually do it
  -- Let me check it again

Checking
-- loop invariant, loop variables: like p = p.next;

What data structures to use:
 - Stack
- PriorityQueue
- TreeMap, TreeSet

Starts from simple solution that works

- First brute force DFS
- brute force DFS + Cache: (easier to write)
- DP

- Save state, existing already known info, use them

X. Left, right array
Scan from left to right or from right to left
Map lastPosMap

left[], right[] maintains some value till current index (ending at idx)

Mistakes/Bugs to check:
- Return right result
- index, or element value?
- do again after while loop

Edge Cases:
- Check code,
  - ==null, whether element can be null
- Element is null
- What if the NestedInteger can be null

Misc
- Map: preSum:index

TreeSet
- floor, higher
TreeMap
- lowerKey, higherKey
- lowerEntry, ceilingEntry

Arrays
- binarySearch
Interval[] sortedIntervals = Arrays.copyOf(intervals,intervals.length);

Character
.isDigit

X. Left right array
Scan from left to right or from right to left
O(N)
- left[], right[]: right[] is not really needed
- leftMin[], LeftMax[], rightMin[], rightMax[]
- the array maintains some value till current index (ending at idx)
  -- runningSum/Product

Lintcode 45 - Maximum Subarray Difference
Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest.

LeetCode 238 - Product of Array Except Self

Given an array arr[], find the maximum j - i such that arr[j] > arr[i]
- leftMin[], rightMax

Maximum Length Bitonic Subarray
- O(1) space: end, start

Related: Longest Bitonic Subsequence
- DP lis[], lds[]

LeetCode 42 - Trapping Rain Water
- two pointers, left, right and maintain leftMax, rightMax
int min = Math.min(leftMax[i], rightMax[i]);
if (height[i] < min) {
  volume += min - height[i];
}
- ordered stack
- leftMax[], rightMax[]

Related: LeetCode 407 - Trapping Rain Water II
- BFS + PriorityQueue
- Add borders first

LeetCode 11 - Container With Most Water
- two pointers