Array
Traversal
- Sum of index is a constant when we travel on the diagonal lines:
i + j = C
.
Problems
In-situ permuation
Solve pretty much all problems related to array rearrangment using O(1) extra memory.
Reference
- Section 7.8, Sedgewick, Robert, and Philippe Flajolet. An introduction to the analysis of algorithms. Addison-Wesley Longman Publishing Co., Inc., 1996.
- Exercise 10-13, 5.2 Internal Sorting. TAOCP Vol 3.
Two Pointer Techniques
Applications
- Array Partition.
- Exchange-based sorting algorithms (bubble sort, quicksort).
- Insertion sort.
Problems
Sliding Windows
Patterns
- Problems related to counting the number of subarray sastifying some conditions.
To count number of subarray inside the range [left, right]
, number of subarrays ending at right
:
cnt = right - left + 1
- May need a dict to hold some statistics of the subarray instead of re-computing for each subarray (normally takes
O(N^3)
).