Two-pointer and sliding window — common interview patterns
Concept
Two-pointer technique: Use two indices (pointers) that move through the data, often reducing an O(n²) brute-force approach to O(n).
Opposite-direction pointers: Start one at the beginning (left = 0) and one at the end (right = n-1). Move them toward each other based on conditions. Used for: two-sum in sorted array, palindrome check, container with most water.
Same-direction pointers (fast/slow): Both start at the beginning, but move at different speeds. Used for: detecting cycles in linked lists (Floyd's tortoise and hare), removing duplicates from sorted array, finding the middle of a linked list.
Sliding window technique: A variant of the two-pointer technique where you maintain a window [left, right] of elements. Expand the window by moving right. Shrink by moving left. The window "slides" through the data.
Fixed-size sliding window: Window always has exactly k elements. Compute the sum/average of each k-length subarray in O(n).
Variable-size sliding window: Expand the window until it violates a constraint, then shrink until it satisfies the constraint. Used for: longest substring without repeating characters, minimum window substring, maximum sum subarray with at most k distinct elements.
When to think "two pointers":
- Sorted array — opposite direction pointers.
- Linked list cycle detection — fast/slow.
- Contiguous subarray sum/length problem — sliding window.
- Remove duplicates in-place — two pointers with one tracking "write position".
Code Example
<?php
// Two-sum in sorted array — O(n) with two pointers
function twoSumSorted(array $sorted, int $target): ?array
{
$left = 0; $right = count($sorted) - 1;
while ($left < $right) {
$sum = $sorted[$left] + $sorted[$right];
if ($sum === $target) return [$left, $right];
if ($sum < $target) $left++; // need bigger sum → move left pointer right
else $right--; // need smaller sum → move right pointer left
}
return null;
}
echo implode(', ', twoSumSorted([1, 2, 3, 4, 6], 6)); // 1, 3 (indices of 2 and 4)
// Palindrome check — O(n) opposite pointers
function isPalindrome(string $s): bool
{
$s = strtolower(preg_replace('/[^a-zA-Z0-9]/', '', $s));
$left = 0; $right = strlen($s) - 1;
while ($left < $right) {
if ($s[$left] !== $s[$right]) return false;
$left++; $right--;
}
return true;
}
echo isPalindrome('A man, a plan, a canal: Panama'); // true
// Sliding window — maximum sum of k consecutive elements
function maxSumSubarray(array $arr, int $k): int
{
$n = count($arr);
$windowSum = array_sum(array_slice($arr, 0, $k));
$maxSum = $windowSum;
for ($i = $k; $i < $n; $i++) {
$windowSum += $arr[$i] - $arr[$i - $k]; // slide: add right, remove left
$maxSum = max($maxSum, $windowSum);
}
return $maxSum;
}
echo maxSumSubarray([2, 1, 5, 1, 3, 2], 3); // 9 (5+1+3)
// Variable sliding window — longest substring without repeating characters
function lengthOfLongestSubstring(string $s): int
{
$charIndex = []; // char → last seen index
$maxLen = 0;
$left = 0;
for ($right = 0; $right < strlen($s); $right++) {
$char = $s[$right];
if (isset($charIndex[$char]) && $charIndex[$char] >= $left) {
$left = $charIndex[$char] + 1; // shrink window: skip past the duplicate
}
$charIndex[$char] = $right;
$maxLen = max($maxLen, $right - $left + 1);
}
return $maxLen;
}
echo lengthOfLongestSubstring('abcabcbb'); // 3 ("abc")
// Fast/slow pointer — detect cycle in linked list
function hasCycle(\ListNode $head): bool
{
$slow = $head; $fast = $head;
while ($fast !== null && $fast->next !== null) {
$slow = $slow->next; // moves 1 step
$fast = $fast->next->next; // moves 2 steps
if ($slow === $fast) return true; // cycle: fast lapped slow
}
return false;
}