Array

1. In-place Manipulation (works for string as well)

   1. usually use two pointer: a slow pointer and a fast pointer

   2. If the output has smaller size than the input, loop forward.

   3. If the output has larger size than the input, assign the full size first and then loop backward.

   4. If the output may have smaller or larger size, assign a new array may be easier than in-place manipulation.

   5. Example question:

      1. leetcode 27_Remove Element

2. Two pointers

   1. One slow, one fast

   2. One loop forward, one loop backward (usually used when we need to check symmetric properties)

   3. Two pointer for two sorted arrays

      1. Example questions:

         1. 88_Merge Sorted Array

         2. 349_Intersection of Two Arrays

         3. 350_Intersection of Two Arrays II

3. Multiple passes

   1. In some questions, it's hard to compete everything in one pass. In this case, we can use two passes or even more.

4. Use dynamic programming

   1. update dynamically (usually the question ask for maximum or minimum)

5. Use hash table/dictionary

   1. If when loop over each element in the array, we need to do a second loop over (at least part of) the array such that these two loops together meets the condition, we can only do one loop and use hash table / set to store the corresponding information.

   2. Example questions:

      1. 1_Two Sum

6. Add Digits and Carry (数组相加要进位)

   1. loop from rightmost to left

   2. set up carry variable to store carry values

   3. typical questions: Q66, Q67

7. Related to intervals

   1. Sort the interval first

   2. Example questions:

      1. 56_Merge Intervals

      2. 57_Insert Interval

Notes

1. When we do loop over the array, it's better to loop over index rather than each element. Because even though we think element is enough at the beginning, we may find we need index later. This happens to me a lot of times!