LC 188 Rotate Array

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4]

Method 1: Slicing operation; take last k elements: nums[-k%n:]

Method 2: Reverse entire array first, then reverse parts. Implement reversal separately without slicing to avoid extra space.

Two Pointers

Opposite Direction Two Pointers

LC 75: Sort Colors

Use pointer i to traverse array, left and right pointers point to next position to fill 0 or 2. First continuously fill 2s, then fill 0s when encountered. Loop condition: i<=r. When i>r, nums[i] must be 2.

15. 3Sum

Two pointers, pay attention to index handling.

Outer pointer needs deduplication, inner two pointers deduplicate each time an answer is found.

Two Sequences

Two Sequence Two Pointers

88. Merge Sorted Arrays

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]

Two pointers should move from end to beginning.

844. Backspace String Compare

Loop condition must be while i>=0 or j>=0. Otherwise when i<0, j>=0, loop ends and returns False, but j might still be on #.

One pointer might need extra movement to consume the entire string. Example: “n” vs “b#n”

Techniques

277. Find the Celebrity

1. Traverse all people to find the only possible candidate

• Initialize candidate=0, enumerate candidates 1 to n-1.
• If knows(candidate, i), candidate cannot be celebrity, update candidate to i
• After traversal, still need to verify if everyone knows candidate

2. For this candidate, traverse all people to confirm if truly celebrity

287. Find the Duplicate Number

Given array of n+1 integers in range [1, n], at least one duplicate exists.

If no duplicates, e.g., [1,3,4,2]. Traverse index: 0 to n-1, map index to nums[index] 0->1->3->2->4->null

With duplicate, e.g., [1,3,4,2,2], since all elements in [1, n], cycle must exist. Answer is cycle start point because i,j exist where nums[i]=nums[j]=x, two nodes point to same node. 0->1->3->2->4->2->4

448. Find All Numbers Disappeared in an Array

Use original array to record which numbers appeared. Imagine another array of length n from 1 to n to track presence.

• If number 4 appears, add n to nums[4-1].
• If all numbers appear, all elements in nums should be > n.

945. Minimum Increment to Make Array Unique

Sort, find maximum value m, count occurrences. Traverse from 1 to m, if cnt[x]>1, push duplicates to next position. Finally, if cnt[m+1]>1, push all extras further.