LeetCode Patterns Flashcards: Two Pointers, Sorted Arrays, Pair Finding, Palindromes

The two pointers pattern uses two index variables that move through the data structure, typically from opposite ends toward the middle or from the same end at different speeds. Use it on sorted arrays or linked lists when you need to find pairs, compare elements, or partition data. The pattern reduces nested loops from O of n squared to O of n by eliminating redundant comparisons. Recognize it when the input is sorted and the problem asks about pairs summing to a target, removing duplicates in place, merging sorted arrays, or checking palindromes.

Place one pointer at the beginning and one at the end of the sorted array. Calculate the sum of elements at both pointers. If the sum equals the target, you found the pair. If the sum is too small, move the left pointer right to increase the sum. If the sum is too large, move the right pointer left to decrease the sum. Each step eliminates one position, so the algorithm runs in O of n time with O of one space. This works because the array is sorted: moving left increases and moving right decreases the sum monotonically. For the unsorted variant, use a hash map instead.

Place one pointer at the start and one at the end of the string. Compare the characters at both pointers. If they match, move both pointers inward. If they do not match, the string is not a palindrome. Continue until the pointers meet or cross. This runs in O of n time and O of one space. For the variant "valid palindrome" that ignores non-alphanumeric characters and case, skip characters that are not letters or digits during traversal and compare lowercase versions.

Sort the array first. For each element, fix it as the first number and use two pointers on the remaining portion to find pairs that sum to the negative of the fixed element, making the total zero. Skip duplicate values for the fixed element to avoid duplicate triplets. Within the two-pointer search, also skip duplicates when a valid triplet is found. The sorting takes O of n log n and the nested two-pointer search takes O of n squared total, making the overall complexity O of n squared. Without sorting and two pointers, the brute force approach would be O of n cubed.

Use a slow pointer to track where the next unique element should be placed and a fast pointer to scan through the array. Start both at the beginning. Move the fast pointer forward. When the fast pointer finds a value different from the element at the slow pointer, increment the slow pointer and copy the fast pointer's value there. After the fast pointer reaches the end, the slow pointer plus one gives the count of unique elements, and the array up to that point contains only unique values. This runs in O of n time and O of one space, modifying the array in place without extra storage.

Place pointers at the leftmost and rightmost bars. Calculate the water area as the minimum of the two heights times the distance between them. Move the pointer at the shorter bar inward because moving the taller bar inward can only decrease or maintain the minimum height while also decreasing width. Moving the shorter bar has a chance of finding a taller bar that increases the constraining height enough to offset the lost width. Track the maximum area found. This runs in O of n time.

The trapping rain water problem asks how much water can be held between bars of varying heights. The key insight is that water above each bar equals the minimum of the maximum height to its left and maximum height to its right, minus the bar's own height. The two-pointer approach uses left and right pointers with running maximums for each side. Process the side with the smaller maximum because you know the water level there is determined by that side. If the current bar is shorter than its side maximum, the difference is trapped water. ---