**Strategy**

- Talking loud

- Always saying/doing

-- 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

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