Master efficient traversal patterns that eliminate nested loops and reduce O(n²) brute force into O(n) solutions. Learn converging pointers, fast/slow patterns, fixed and variable windows, and specialized techniques for interviews.
Two pointers is a fundamental technique that uses multiple index variables to traverse data structures efficiently, reducing time complexity from O(n²) to O(n) by eliminating nested loops through intelligent pointer movement.
Naive brute force approaches often use nested loops. For example, finding a pair that sums to a target in a sorted array is O(n²) with nested loops. Two pointers reduce this to O(n) with a single pass using converging indices.
Key Insight: When moving a pointer, we can make smart decisions about what to check next based on problem constraints, eliminating the need to check all combinations.
Converging pointers start at opposite ends of an array and move inward. This pattern is ideal for sorted arrays and problems where we need to find pairs or validate properties.
Start with pointers at both ends. If sum equals target, return. If sum is too small, move left pointer right (increase sum). If sum is too large, move right pointer left (decrease sum).
int[] TwoSumII(int[] nums, int target) { int left = 0, right = nums.Length - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { return new[] { left + 1, right + 1 }; } else if (sum < target) { left++; } else { right--; } } return new[] { -1, -1 }; }
Example: nums = [2,7,11,15], target = 9. Start: left=0 (2), right=3 (15), sum=17 > 9, move right left. left=0 (2), right=2 (11), sum=13 > 9, move right left. left=0 (2), right=1 (7), sum=9, return [1,2].
Sort array first. For each element, use two-pointer technique to find pairs that sum to negative of current element. Skip duplicates to avoid duplicate triplets.
IList<IList<int>> ThreeSum(int[] nums) { var result = new List<IList<int>>(); if (nums == null || nums.Length < 3) return result; Array.Sort(nums); for (int i = 0; i < nums.Length - 2; i++) { // Skip duplicates for outer loop if (i > 0 && nums[i] == nums[i - 1]) continue; // If smallest possible sum is positive, break if (nums[i] > 0) break; int left = i + 1, right = nums.Length - 1; int target = -nums[i]; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { result.Add(new List<int> { nums[i], nums[left], nums[right] }); // Skip duplicates for left pointer while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates for right pointer while (left < right && nums[right] == nums[right - 1]) right--; left++; right--; } else if (sum < target) { left++; } else { right--; } } } return result; }
Example: nums = [-1, 0, 1, 2, -1, -4]. After sort: [-4, -1, -1, 0, 1, 2]. For i=0 (nums[i]=-4), target=4, no valid pairs. For i=1 (nums[i]=-1), target=1, find -1+2=1. Result includes [-1,-1,2] and [-1,0,1].
Start with widest container. Area is limited by shorter line. Move the shorter line inward, hoping to find a taller line that increases area. Moving the taller line can only decrease area (width decreases, height limited by shorter line).
int MaxArea(int[] height) { int left = 0, right = height.Length - 1; int maxArea = 0; while (left < right) { // Calculate current area int width = right - left; int h = Math.Min(height[left], height[right]); int area = width * h; maxArea = Math.Max(maxArea, area); // Move shorter line inward if (height[left] < height[right]) { left++; } else { right--; } } return maxArea; }
Example: height = [1,8,6,2,5,4,8,3,7]. Start: left=0 (1), right=8 (7), area = min(1,7)×8 = 8. Move left (1 < 7). Continue moving until finding optimal pairing. Maximum area is 49 (8 and 7 at indices 1 and 8 gives 7×7=49).
Use two pointers from start and end. Skip non-alphanumeric characters. Compare characters at both pointers (case-insensitive). If mismatch, not palindrome. If reach center, is palindrome.
bool IsPalindrome(string s) { int left = 0, right = s.Length - 1; while (left < right) { // Skip non-alphanumeric from left while (left < right && !char.IsLetterOrDigit(s[left])) { left++; } // Skip non-alphanumeric from right while (left < right && !char.IsLetterOrDigit(s[right])) { right--; } // Compare characters (case-insensitive) if (char.ToLower(s[left]) != char.ToLower(s[right])) { return false; } left++; right--; } return true; }
Example: s = "A man, a plan, a canal: Panama". After filtering alphanumeric: "AmanaplanacanalPanama". Compare: A==a, m==m, a==a, etc. Returns true.
Water at any position is determined by the maximum height to its left and maximum height to its right. Use two pointers and track max heights. Move pointer with smaller max height toward center, as that determines water level at that position.
int Trap(int[] height) { if (height == null || height.Length == 0) return 0; int left = 0, right = height.Length - 1; int leftMax = 0, rightMax = 0; int water = 0; while (left < right) { // Update maxes leftMax = Math.Max(leftMax, height[left]); rightMax = Math.Max(rightMax, height[right]); // Water level determined by smaller max height if (leftMax < rightMax) { // Left side determines water level water += leftMax - height[left]; left++; } else { // Right side determines water level water += rightMax - height[right]; right--; } } return water; }
Example: height = [0,1,0,2,1,0,1,3,2,1,2,1]. Visualize as bars. At index 2 (height 0), leftMax=1, rightMax=3, water=min(1,3)-0=1. Total trapped water = 6 units.
Both pointers move in the same direction but at different speeds. The slow pointer processes/writes, while the fast pointer scans ahead. Commonly used for in-place modifications and cycle detection.
Slow pointer marks position to write next unique element. Fast pointer scans for different elements. When found, write to slow pointer position and advance both.
int RemoveDuplicates(int[] nums) { if (nums.Length == 0) return 0; int slow = 0; for (int fast = 1; fast < nums.Length; fast++) { // Found new unique element if (nums[fast] != nums[slow]) { slow++; nums[slow] = nums[fast]; } } return slow + 1; }
Example: nums = [1,1,2,2,2,3]. slow=0 (1), fast moves: 1 (dup skip), 2 (new, slow=1, nums[1]=2), 2 (dup), 2 (dup), 3 (new, slow=2, nums[2]=3). Return 3. Array becomes [1,2,3,...].
Slow pointer tracks position for next non-zero element. Fast pointer scans entire array. When non-zero found, swap with slow pointer position.
void MoveZeroes(int[] nums) { int slow = 0; for (int fast = 0; fast < nums.Length; fast++) { // Found non-zero element if (nums[fast] != 0) { // Swap int temp = nums[slow]; nums[slow] = nums[fast]; nums[fast] = temp; slow++; } } }
Example: nums = [0,1,0,3,12]. slow=0, fast scans: 0 (skip), 1 (swap with slow[0], slow=1), 0 (skip), 3 (swap with slow[1], slow=2), 12 (swap with slow[2]). Result: [1,3,12,0,0].
Slow pointer moves 1 step, fast pointer moves 2 steps. If they meet, cycle exists. If fast reaches null, no cycle. Mathematically proven: they will meet in cycle if exists.
public class ListNode { public int val; public ListNode next; } bool HasCycle(ListNode head) { if (head == null) return false; ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; }
Why it works: If cycle exists with length C, and fast is 1 step ahead in cycle, gap closes by 1 each iteration. When fast enters cycle, slow is still outside. Fast laps slow, guaranteeing meeting point.
Slow and fast pointers start at head. Slow moves 1 step, fast moves 2. When fast reaches end, slow is at middle.
ListNode MiddleNode(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }
Example: List 1→2→3→4→5. Slow and fast start at 1. After iterations: fast reaches 5 (or null after), slow at 3. Return node 3.
Use slow and fast pointers on the sequence of transformations. If they meet, cycle detected (unhappy). If slow reaches 1, happy number.
bool IsHappy(int n) { int slow = n, fast = n; do { slow = SumOfSquares(slow); fast = SumOfSquares(SumOfSquares(fast)); if (fast == 1) return true; } while (slow != fast); return slow == 1; } int SumOfSquares(int n) { int sum = 0; while (n > 0) { int digit = n % 10; sum += digit * digit; n /= 10; } return sum; }
Example: n = 7. Sequence: 7→49→97→130→10→1. Slow reaches 1 before meeting fast, returns true.
Fixed sliding window maintains a window of constant size and slides it across the array. Ideal for problems asking for max/min/average over subarrays of specific length.
int FixedWindowTemplate(int[] nums, int k) { // Initialize window with first k elements int windowSum = 0; for (int i = 0; i < k; i++) { windowSum += nums[i]; } int maxSum = windowSum; // Slide window: remove left element, add right element for (int i = k; i < nums.Length; i++) { windowSum = windowSum - nums[i - k] + nums[i]; maxSum = Math.Max(maxSum, windowSum); } return maxSum; }
Build window sum with first k elements. Slide window by removing leftmost, adding rightmost. Track maximum sum throughout.
int MaxSumSubarray(int[] nums, int k) { if (nums.Length < k) return 0; // Calculate sum of first k elements int windowSum = 0; for (int i = 0; i < k; i++) { windowSum += nums[i]; } int maxSum = windowSum; // Slide the window for (int i = k; i < nums.Length; i++) { // Remove leftmost element of previous window windowSum -= nums[i - k]; // Add new rightmost element windowSum += nums[i]; // Update maximum maxSum = Math.Max(maxSum, windowSum); } return maxSum; }
Example: nums = [1,3,2,6,-1,4,1,8], k = 3. Windows: [1,3,2]=6, [3,2,6]=11, [2,6,-1]=7, [6,-1,4]=9, [-1,4,1]=4, [4,1,8]=13. Maximum = 13.
Count character frequencies in s1. Slide window of same size on s2. Check if any window matches s1's frequency.
bool CheckInclusion(string s1, string s2) { if (s1.Length > s2.Length) return false; // Count characters in s1 int[] s1Count = new int[26]; for (int i = 0; i < s1.Length; i++) { s1Count[s1[i] - 'a']++; } // Check each window of size s1.length in s2 int[] windowCount = new int[26]; for (int i = 0; i < s2.Length; i++) { // Add new character to window windowCount[s2[i] - 'a']++; // Remove character that exits window if (i >= s1.Length) { windowCount[s2[i - s1.Length] - 'a']--; } // Check if window matches s1 if (ArraysEqual(s1Count, windowCount)) { return true; } } return false; } bool ArraysEqual(int[] a, int[] b) { for (int i = 0; i < a.Length; i++) { if (a[i] != b[i]) return false; } return true; }
Example: s1 = "ab", s2 = "eidbccbacd". s1Count = {a:1, b:1}. Check windows: "ei" no, "id" no, "db" no, "bc" no, "cc" no, "cb" no, "ba" yes (contains "ab" permutation). Return true.
Similar to permutation check, but return all matching positions instead of boolean. Slide window and compare at every position.
IList<int> FindAnagrams(string s, string p) { var result = new List<int>(); if (p.Length > s.Length) return result; // Count characters in pattern p int[] pCount = new int[26]; for (int i = 0; i < p.Length; i++) { pCount[p[i] - 'a']++; } // Slide window over string s int[] windowCount = new int[26]; for (int i = 0; i < s.Length; i++) { // Add new character windowCount[s[i] - 'a']++; // Remove old character if (i >= p.Length) { windowCount[s[i - p.Length] - 'a']--; } // Check if match at window position if (i >= p.Length - 1 && ArraysEqual(pCount, windowCount)) { result.Add(i - p.Length + 1); } } return result; }
Example: s = "cbaebabacd", p = "abc". Anagrams at indices: position 0 ("cba"), position 6 ("bac"). Return [0, 6].
Variable window expands to include elements and contracts to satisfy constraints. Use when finding min/max subarrays matching criteria. Pattern: expand right until condition met, then contract left to minimize/maximize.
int VariableWindowTemplate(int[] nums) { int left = 0, result = 0; var windowMap = new Dictionary<int, int>(); for (int right = 0; right < nums.Length; right++) { // Add right element to window if (!windowMap.ContainsKey(nums[right])) { windowMap[nums[right]] = 0; } windowMap[nums[right]]++; // Contract window while condition not met while (/* condition check */ false) { windowMap[nums[left]]--; if (windowMap[nums[left]] == 0) { windowMap.Remove(nums[left]); } left++; } // Update result with valid window result = Math.Max(result, right - left + 1); } return result; }
Step 1: Build frequency map of target string t. Step 2: Expand window by moving right pointer until all characters are included. Step 3: Contract window by moving left pointer while still valid. Step 4: Track minimum window found.
string MinWindow(string s, string t) { if (s == null || t == null || s.Length == 0 || t.Length == 0) { return ""; } // Dictionary to keep count of characters in t var dictT = new Dictionary<char, int>(); foreach (char c in t) { if (!dictT.ContainsKey(c)) dictT[c] = 0; dictT[c]++; } // required: number of unique characters in t that need to be present int required = dictT.Count; // formed: number of unique characters in current window with desired frequency int formed = 0; // windowCounts: current window's character frequency var windowCounts = new Dictionary<char, int>(); int left = 0, right = 0; int minLen = int.MaxValue; int minLeft = 0; while (right < s.Length) { // Add character from right to window char c = s[right]; if (!windowCounts.ContainsKey(c)) windowCounts[c] = 0; windowCounts[c]++; // If character frequency matches target, increment formed if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) { formed++; } // Contract from left while window is valid while (left <= right && formed == required) { c = s[left]; // Save minimum window if (right - left + 1 < minLen) { minLen = right - left + 1; minLeft = left; } // Remove from left windowCounts[c]--; if (dictT.ContainsKey(c) && windowCounts[c] < dictT[c]) { formed--; } left++; } right++; } return minLen == int.MaxValue ? "" : s.Substring(minLeft, minLen); }
Example: s = "ADOBECODEBANC", t = "ABC". Build dictT = {A:1, B:1, C:1}. Expand right until window "ADOBEC" is valid (contains all). Contract left: "DOBEC", "OBEC", "BEC" - contracts too far. Continue expanding/contracting. Minimum window = "BANC".
Expand window by moving right pointer. Track character positions. If character repeats, move left pointer to after previous occurrence. Update maximum length.
int LengthOfLongestSubstring(string s) { var charIndex = new Dictionary<char, int>(); int left = 0, maxLen = 0; for (int right = 0; right < s.Length; right++) { char c = s[right]; // If character exists in window, move left if (charIndex.ContainsKey(c) && charIndex[c] >= left) { left = charIndex[c] + 1; } // Update character's latest position charIndex[c] = right; // Update maximum length maxLen = Math.Max(maxLen, right - left + 1); } return maxLen; }
Example: s = "abcabcbb". Window: "a"(1), "ab"(2), "abc"(3), "bcab"(4, move left past "a"), "cabcbb"→"abcb"(4), "bcb"(3). Maximum = 3 ("abc").
Expand window by right pointer. Track character frequencies. Valid window: windowLength - maxFrequency ≤ k (changes needed ≤ k). Contract window if invalid. Update maximum length.
int CharacterReplacement(string s, int k) { int[] count = new int[26]; int left = 0, maxFreq = 0, maxLen = 0; for (int right = 0; right < s.Length; right++) { // Add right character count[s[right] - 'A']++; maxFreq = Math.Max(maxFreq, count[s[right] - 'A']); // Contract window if too many changes needed // changes needed = window size - most frequent character while ((right - left + 1) - maxFreq > k) { count[s[left] - 'A']--; left++; } // Update maximum length maxLen = Math.Max(maxLen, right - left + 1); } return maxLen; }
Example: s = "ABAB", k = 2. Window "A"(1, 0 changes), "AB"(2, 1 change), "ABA"(3, 1 change), "ABAB"(4, 2 changes). Result = 4 (replace 2 B's with A or vice versa).
This is longest subarray with at most 2 distinct elements. Expand window with right pointer. Track fruit counts. If more than 2 types, contract from left.
int TotalFruit(int[] fruits) { var fruitCount = new Dictionary<int, int>(); int left = 0, maxFruits = 0; for (int right = 0; right < fruits.Length; right++) { // Add fruit to right of window if (!fruitCount.ContainsKey(fruits[right])) { fruitCount[fruits[right]] = 0; } fruitCount[fruits[right]]++; // Shrink window if more than 2 types while (fruitCount.Count > 2) { fruitCount[fruits[left]]--; if (fruitCount[fruits[left]] == 0) { fruitCount.Remove(fruits[left]); } left++; } // Update maximum fruits maxFruits = Math.Max(maxFruits, right - left + 1); } return maxFruits; }
Example: fruits = [1,2,1,2,3]. Window: [1]=1, [1,2]=2, [1,2,1]=3, [1,2,1,2]=4, hits 3 types, contract to [2,1,2]=3, then [1,2,3] still 3 types, contract to [2,3]=2. Maximum = 4.
Prefix sum arrays enable O(1) range sum queries after O(n) preprocessing. Used for subarray sum problems and combined with hashmap for target sum finding.
Prefix sum at index i = sum of all elements from index 0 to i. Range sum from i to j = prefix[j+1] - prefix[i].
// Build prefix sum array int[] BuildPrefixSum(int[] nums) { int[] prefix = new int[nums.Length + 1]; prefix[0] = 0; for (int i = 1; i <= nums.Length; i++) { prefix[i] = prefix[i - 1] + nums[i - 1]; } return prefix; } // Query range sum [left, right] O(1) int RangeSum(int[] prefix, int left, int right) { return prefix[right + 1] - prefix[left]; }
Key Insight: If prefix sum at index j minus prefix sum at index i equals k, then subarray [i+1, j] sums to k. Use hashmap to count prefix sums. For each position, check if (currentSum - k) exists in map.
int SubarraySum(int[] nums, int k) { var sumCount = new Dictionary<int, int>(); // Initialize with 0 sum appearing once (empty subarray) sumCount[0] = 1; int currentSum = 0, count = 0; foreach (int num in nums) { currentSum += num; // Check if (currentSum - k) exists in map int target = currentSum - k; if (sumCount.ContainsKey(target)) { count += sumCount[target]; } // Add current sum to map if (!sumCount.ContainsKey(currentSum)) { sumCount[currentSum] = 0; } sumCount[currentSum]++; } return count; }
Example: nums = [1,1,1], k = 2. Prefix sums: 0, 1, 2, 3. At index 1 (sum=2): check 2-2=0, found, count=1. At index 2 (sum=3): check 3-2=1, found, count=2. Subarrays: [1,1] at indices 0-1 and 1-2. Return 2.
2D prefix sum: include row, column, and diagonal interactions. Formula: prefix[r][c] = matrix[r][c] + prefix[r-1][c] + prefix[r][c-1] - prefix[r-1][c-1].
public class NumMatrix { private int[][] prefix; public NumMatrix(int[][] matrix) { int rows = matrix.Length; int cols = matrix[0].Length; prefix = new int[rows + 1][]; for (int i = 0; i <= rows; i++) { prefix[i] = new int[cols + 1]; } // Build 2D prefix sum for (int r = 1; r <= rows; r++) { for (int c = 1; c <= cols; c++) { prefix[r][c] = matrix[r - 1][c - 1] + prefix[r - 1][c] + prefix[r][c - 1] - prefix[r - 1][c - 1]; } } } public int SumRegion(int row1, int col1, int row2, int col2) { return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] - prefix[row2 + 1][col1] + prefix[row1][col1]; } }
Example: Matrix [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5]]. Query sum from (1,1) to (2,2) returns 11 (6+3+2+0=11).
Use two passes: left products (prefix products) and right products (suffix products). Result[i] = left[i] × right[i].
int[] ProductExceptSelf(int[] nums) { int n = nums.Length; int[] result = new int[n]; // First pass: compute left products (prefix) // result[i] = product of all elements to left of i result[0] = 1; for (int i = 1; i < n; i++) { result[i] = result[i - 1] * nums[i - 1]; } // Second pass: compute right products and multiply // Traverse right to left, tracking suffix product int rightProduct = 1; for (int i = n - 1; i >= 0; i--) { result[i] *= rightProduct; rightProduct *= nums[i]; } return result; }
Example: nums = [1,2,3,4]. Left products: [1,1,2,6]. Right products computed in reverse: [24,12,4,1]. Results: [1×24, 1×12, 2×4, 6×1] = [24,12,8,6].
Three-pointer technique for partitioning arrays into three sections. Classic problem: sort array with three distinct values (0, 1, 2) in single pass.
Approach: Partition array into [0..left] for 0s, [left+1..mid] for 1s, [mid+1..right] for 2s. Pointer mid scans array. If nums[mid]=0, swap with left, advance both. If nums[mid]=1, advance mid. If nums[mid]=2, swap with right, move right backward.
void SortColors(int[] nums) { int left = 0, mid = 0, right = nums.Length - 1; while (mid <= right) { if (nums[mid] == 0) { // Swap with left pointer, advance both int temp = nums[left]; nums[left] = nums[mid]; nums[mid] = temp; left++; mid++; } else if (nums[mid] == 1) { // Just advance mid mid++; } else { // nums[mid] == 2, swap with right, move right back int temp = nums[mid]; nums[mid] = nums[right]; nums[right] = temp; right--; } } }
Example: nums = [2,0,2,1,1,0]. Start: left=0, mid=0, right=5. Process: nums[0]=2 → swap with right[5]=0, nums=[0,0,2,1,1,2]. Continue: left=1, mid=1, nums[1]=0 → swap with left[1], but already 0. Advance both. Eventually: [0,0,1,1,2,2].
Handling overlapping intervals using two pointers or efficient merging. Common in scheduling, meeting room problems, and interval union queries.
Algorithm: Sort intervals by start. Iterate through, merging if current start ≤ previous end. Track merged end across overlapping intervals.
int[][] Merge(int[][] intervals) { if (intervals.Length <= 1) { return intervals; } // Sort by start time System.Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0])); var result = new List<int[]>(); int[] current = intervals[0]; for (int i = 1; i < intervals.Length; i++) { if (intervals[i][0] <= current[1]) { // Merge: extend end of current current[1] = Math.Max(current[1], intervals[i][1]); } else { // No overlap: add current to result, move to next result.Add(current); current = intervals[i]; } } // Add the last interval result.Add(current); return result.ToArray(); }
Example: intervals = [[1,3],[2,6],[8,10],[15,18]]. After sort (already sorted). Merge [1,3] and [2,6] to [1,6]. [8,10] doesn't overlap. [15,18] doesn't overlap. Result: [[1,6],[8,10],[15,18]].
Two pointers, one for each list. At each step, find intersection of current intervals. If current intervals overlap, intersection is [max(starts), min(ends)]. Move pointer of interval that ends first.
int[][] IntervalIntersection(int[][] list1, int[][] list2) { var result = new List<int[]>(); int i = 0, j = 0; while (i < list1.Length && j < list2.Length) { int start = Math.Max(list1[i][0], list2[j][0]); int end = Math.Min(list1[i][1], list2[j][1]); // If overlapping, add intersection if (start <= end) { result.Add(new int[] { start, end }); } // Move pointer of interval that ends first if (list1[i][1] < list2[j][1]) { i++; } else { j++; } } return result.ToArray(); }
Example: list1 = [[0,2],[5,10]], list2 = [[1,3],[5,7]]. Compare [0,2] and [1,3]: intersection [1,2]. [0,2] ends first, move i. Compare [5,10] and [1,3]: no overlap. Compare [5,10] and [5,7]: intersection [5,7]. Result: [[1,2],[5,7]].
Use this flowchart to identify which technique applies to your problem:
| Pattern | Use Case | Time | Space | Key Constraint |
|---|---|---|---|---|
| Opposite Pointers | Pairs, palindromes, container | O(n) | O(1) | Usually sorted |
| Fast/Slow Pointers | Cycle detection, middle, duplicates | O(n) | O(1) | Linked list or array traversal |
| Fixed Window | Max/min over k-size windows | O(n) | O(k) or O(26) | Fixed window size |
| Variable Window | Min/max substring with conditions | O(n) | O(n) hashmap | Expand/contract dynamically |
| Prefix Sum | Range sum, subarray sums | O(n) build, O(1) query | O(n) | Multiple queries needed |
| Dutch Flag | Partition, sort 3 values | O(n) | O(1) | Three distinct values |
| Merge Intervals | Overlapping intervals | O(n log n) | O(n) | Sort first |
Many hard problems combine patterns:
Easy: Two Sum II (sorted), Valid Palindrome, Remove Duplicates, Move Zeroes. Build fundamentals with simple pointer movement.
Medium: 3Sum, Container with Most Water, Longest Substring Without Repeating, Merge Intervals. Combine patterns and handle edge cases.
Hard: Trapping Rain Water, Minimum Window Substring, Subarray Sum Equals K, 4Sum II. Mix multiple techniques, optimize space/time.