Core Concepts

• 1Two pointer technique — convergent: place one pointer at the start, one at the end. Move them toward each other based on a condition. Classic use case: finding a pair that sums to a target in a sorted array. Instead of O(n²) nested loops, you move left pointer right when sum is too small, right pointer left when sum is too large — O(n) total. The key insight: because the array is sorted, you have perfect information about which direction to move each pointer. Works for: two-sum in sorted array, three-sum (fix one, two-pointer the rest), container with most water, trapping rain water.
• 2Two pointer technique — fast/slow (Floyd's algorithm): one pointer moves one step at a time, the other moves two. If there's a cycle, they will meet inside it. Used to detect cycles in linked lists, find the middle of a linked list (stop when fast reaches end), and detect duplicate numbers in arrays. For finding the middle: when fast reaches the end, slow is at the middle — useful for merge sort and palindrome checking.
• 3Sliding window — fixed size: maintain a window of exactly k elements. To slide: add the new right element, subtract the old left element. Example: maximum sum subarray of size k — compute the sum of the first k elements, then slide right and update in O(1) per step. Total O(n). Template: initialize window sum for first k elements; for i from k to n: sum += arr[i] - arr[i-k]; update result.
• 4Sliding window — variable size: expand right pointer until the window is invalid; shrink from the left until valid again. Example: smallest subarray with sum ≥ target. Right pointer always moves forward (n times total). Left pointer also only moves forward (n times total). Total O(n) — not O(n²) even though there's a nested while loop, because each pointer traverses the array at most once. Template: left=0, result=inf; for right in range(n): add arr[right]; while window invalid: subtract arr[left], left++; update result.
• 5Prefix sums: precompute prefix[i] = arr[0] + arr[1] + ... + arr[i-1]. Then sum(arr[l..r]) = prefix[r+1] - prefix[l] in O(1). Build prefix in O(n), answer each range sum query in O(1). Extension: 2D prefix sums for matrix region sum queries. Critical use case: subarray sum equals k — for each right index, check how many left indices have prefix[right] - prefix[left] = k, equivalently prefix[right] - k has been seen before. Use a hashmap of {prefix_sum: count}.
• 6Kadane's algorithm for maximum subarray: the key insight is: the maximum subarray ending at index i either (a) extends the maximum subarray ending at i-1, or (b) starts fresh at i. So: current_max = max(arr[i], current_max + arr[i]). Global max = max over all i of current_max. O(n) time, O(1) space. Handles negative numbers correctly. Variation: maximum product subarray requires tracking both max and min (because negative × negative = positive).
• 7In-place array manipulation: many problems ask you to modify an array without extra space. Common techniques: (1) Use the array values as indices to mark visited positions (negation trick): if arr[abs(arr[i])-1] > 0, negate it to mark that value i was seen. (2) Two pointers for removing duplicates: keep a 'write pointer' that only advances when a new unique element is found. (3) Dutch National Flag (3-way partition): three pointers for values 0, 1, 2 — sort in a single pass. (4) Rotation: reverse subarrays — reverse whole array, reverse first k, reverse last n-k.

Key Patterns & Templates