Skip to main content

Left / Right Heads

Two pointers start at opposite ends - left at the front, right at the back - and move towards each other, stopping when they meet. Each step either advances one pointer past an element to skip, or acts on the pair (compare, swap) and moves both inward.

Classic​

125. Valid Palindrome​

Easy·
Explanation

A palindrome reads the same forwards and backwards. The trick is that we need to ignore non-alphanumeric characters and treat upper and lower case as equal. Rather than cleaning the string first, we can handle these conditions on the fly with two converging pointers.

Setup:

  • Place left at the start and right at the end of the string.

Scan:

  • If s[left] is not alphanumeric, skip it by advancing left inward.
  • If s[right] is not alphanumeric, skip it by retreating right inward.
  • Otherwise, both pointers sit on alphanumeric characters - compare them case-insensitively.
    • If they differ, the string is not a palindrome; return False immediately.
    • If they match, move both pointers inward and continue.

Result:

  • If the pointers cross without finding a mismatch, every alphanumeric character has a valid mirror - return True.
Analysis
Time
O(N)
  • N is the length of the string. Each character is visited at most once by either pointer.
Space
O(1)
  • Only two integer pointers are used; no copy of the string is made.
FIG. 125 VALID PALINDROME● INTERACTIVE
visualization loads as you reach it
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
elif not s[right].isalnum():
right -= 1
elif s[left].lower() != s[right].lower():
return False
else:
left += 1
right -= 1
return True

Reverse a Subarray​

344. Reverse String​

Easy·
Explanation

Reversing a character array in place is exactly what the generic reverseSubArray helper does. Here we just call it on the entire array, from index 0 to index len(s) - 1.

How it works:

  • The helper places left at the first element and right at the last.
  • Each iteration swaps the outer pair and moves both pointers inward.
  • When the pointers cross, every character has been mirrored and the array is fully reversed.

In-place constraint:

  • The problem requires O(1) extra memory. The helper only allocates one tmp variable per swap, satisfying this constraint.
Analysis
Time
O(n)
  • n = len(s). left and right each move inward one step per iteration until they cross, so together they visit every element exactly once.
Space
O(1)
  • Only the single tmp variable is used per swap; the reversal is done in place.
FIG. 344 REVERSE STRING● INTERACTIVE
visualization loads as you reach it
def reverseSubArray(arr, left, right): # right is inclusive
while left < right:
tmp = arr[right]
arr[right] = arr[left]
arr[left] = tmp
left += 1
right -= 1
 
 
class Solution:
def reverseString(self, s: List[str]) -> None:
reverseSubArray(s, 0, len(s) - 1) # inplace

541. Reverse String II​

Easy·
Explanation

The rule is: for every chunk of 2k characters, reverse only the first k characters. If the remaining tail is fewer than k characters, reverse all of them; if the tail is between k and 2k, reverse only the first k and leave the rest untouched.

Setup:

  • Convert the string to a list so we can do in-place swaps.
  • Step through the string with a jump of 2k, landing on the start of each chunk.

Per-chunk reversal:

  • For chunk starting at i, we want to reverse indices i to i + k - 1.
  • The min(i + k - 1, n - 1) guard handles the tail case: if fewer than k characters remain, we reverse up to the last available index instead.

Result:

  • Join the list back into a string and return.

The reverseSubArray helper handles each reversal in O(k) with two converging pointers.

Analysis
Time
O(n)
  • The for i in range(0, n, 2 * k) loop visits each chunk once, and reverseSubArray reverses at most k characters per chunk, so across all chunks each of the n characters is swapped at most once, where n = len(s).
Space
O(n)
  • s = list(s) converts the string to a list of characters for in-place mutation, requiring O(n) extra space.
FIG. 541 REVERSE STRING II● INTERACTIVE
visualization loads as you reach it
def reverseSubArray(arr, left, right): # right is inclusive
while left < right:
tmp = arr[right]
arr[right] = arr[left]
arr[left] = tmp
left += 1
right -= 1
 
 
class Solution:
def reverseStr(self, s: str, k: int) -> str:
n = len(s)
s = list(s)
for i in range(0, n, 2 * k):
reverseSubArray(s, i, min(i + k - 1, n - 1))
return "".join(s)

2000. Reverse Prefix of Word​

Easy·
Explanation

We need to find the first occurrence of a character ch in the word and reverse everything from the start up to and including that character.

Setup:

  • Convert the string to a list for in-place modification.

Scan:

  • Walk through the list with index right.
  • The moment word[right] == ch, we have found the boundary.
  • Call reverseSubArray(word, 0, right) to reverse the prefix [0, right], then break immediately.

No match:

  • If ch does not appear in the word, the loop completes without calling reverseSubArray and the word is returned unchanged.

Result:

  • Join the list back into a string and return.
Analysis
Time
O(N)
  • N is the length of the word. The scan is O(N) in the worst case, and the reversal is at most O(N).
Space
O(N)
  • The string is converted to a list for in-place mutation.
FIG. 2000 REVERSE PREFIX OF WORD● INTERACTIVE
visualization loads as you reach it
def reverseSubArray(arr, left, right): # right is inclusive
while left < right:
tmp = arr[right]
arr[right] = arr[left]
arr[left] = tmp
left += 1
right -= 1
 
 
class Solution:
def reversePrefix(self, word: str, ch: str) -> str:
n = len(word)
word = list(word)
for right in range(n):
if word[right] == ch:
reverseSubArray(word, 0, right)
break
return "".join(word)

151. Reverse Words in a String​

Medium·
Explanation

The key insight is a two-step reversal trick: reversing the entire array puts the words in the right order (last word first becomes first word last), but each individual word is now spelled backwards. A second pass reverses each word back to its correct spelling.

Step 1 - Clean whitespace:

  • " ".join(s.split()) collapses all leading, trailing, and consecutive internal spaces into single spaces. This normalises the input so word boundaries are always single spaces.

Step 2 - Reverse the whole string:

  • Convert to a list and call reverseSubArray(s, 0, n - 1). After this, the word order is reversed but every word's characters are reversed too.

Step 3 - Reverse each word:

  • Walk with right. Whenever we hit a space, the word [left, right - 1] is complete - reverse it back. Then advance left past the space.
  • After the loop ends, reverse the last word [left, right] (there is no trailing space to trigger it).

Result:

  • Join and return the now-correctly-ordered string.
Analysis
Time
O(N)
  • N is the length of the string. Cleaning, the whole-array reversal, and all per-word reversals each touch every character at most once.
Space
O(N)
  • The string is converted to a list. The split() + join() also allocates a new string.
FIG. 151 REVERSE WORDS IN A STRING● INTERACTIVE
visualization loads as you reach it
def reverseSubArray(arr, left, right): # right is inclusive
while left < right:
tmp = arr[right]
arr[right] = arr[left]
arr[left] = tmp
left += 1
right -= 1
 
 
class Solution:
def reverseWords(self, s: str) -> str:
s = " ".join(s.split()) # cleans all the redundant whitespaces
n = len(s)
s = list(s)
reverseSubArray(s, 0, n - 1) # reverse entire array
left = 0
for right in range(n):
if s[right] == " ":
reverseSubArray(s, left, right - 1)
left = right + 1
reverseSubArray(s, left, right)
return "".join(s)

186. Reverse Words in a String II​

Medium·
Explanation

This is the in-place variant of problem 151. The input is already a character array with exactly one space between words and no leading or trailing spaces, so there is no whitespace-cleaning step. The same two-step reversal trick applies.

Step 1 - Reverse the whole array:

  • reverseSubArray(s, 0, n - 1) puts words in the right order but reverses each word's characters.

Step 2 - Reverse each word back:

  • Walk right through the array. When s[right] == ' ', the word at [left, right - 1] is complete - reverse it. Then set left = right + 1.
  • After the loop, right sits at the last index (n - 1) and the last word [left, right] still needs to be reversed.

In-place constraint:

  • No new list is allocated; all operations mutate the input array directly. The helper only uses a single tmp variable.
Analysis
Time
O(2n)
  • n is the length of s. One O(n) pass fully reverses the array, then a second O(n) pass (summed across all the per-word reverseSubArray calls) reverses each word back - 2n.
Space
O(1)
  • The reversal is done in place; reverseSubArray only uses a constant number of extra variables (tmp, left, right).
FIG. 186 REVERSE WORDS IN A STRING II● INTERACTIVE
visualization loads as you reach it
def reverseSubArray(arr, left, right): # right is inclusive
while left < right:
tmp = arr[right]
arr[right] = arr[left]
arr[left] = tmp
left += 1
right -= 1
 
 
class Solution:
def reverseWords(self, s: List[str]) -> None:
n = len(s)
reverseSubArray(s, 0, n - 1)
left = 0
for right in range(n):
if s[right] == " ":
reverseSubArray(s, left, right - 1)
left = right + 1
reverseSubArray(s, left, right)

557. Reverse Words in a String III​

Easy·
Explanation

Unlike problems 151 and 186, here we want to reverse each word individually while keeping the word order and spacing intact. There is no full-array reversal step - we just scan for word boundaries and reverse each word in place.

Setup:

  • Convert the string to a list for in-place swaps.
  • left tracks the start of the current word.

Scan:

  • Walk right through the list. When we hit a space, the word [left, right - 1] is complete - call reverseSubArray on it. Then advance left to right + 1 to start tracking the next word.

Last word:

  • After the loop, right sits at the last index and the final word [left, right] has not been reversed yet - reverse it now.

Result:

  • Join the list and return the string.
Analysis
Time
O(N)
  • N is the length of the string. The scan and all per-word reversals together touch each character at most twice.
Space
O(N)
  • The string is converted to a mutable list of characters.
FIG. 557 REVERSE WORDS IN A STRING III● INTERACTIVE
visualization loads as you reach it
def reverseSubArray(arr, left, right): # right is inclusive
while left < right:
tmp = arr[right]
arr[right] = arr[left]
arr[left] = tmp
left += 1
right -= 1
 
 
class Solution:
def reverseWords(self, s: str) -> str:
n = len(s)
s = list(s)
left = 0
for right in range(n):
if s[right] == " ":
reverseSubArray(s, left, right - 1)
left = right + 1
reverseSubArray(s, left, right)
return "".join(s)

Reverse Individual Elements​

345. Reverse Vowels of a String​

Easy·
Explanation

We want to swap only the vowels in the string, leaving all consonants and other characters in their original positions. Two converging pointers let us find the next eligible pair to swap without allocating extra space for vowel indices.

Setup:

  • Convert the string to a list for in-place swaps.
  • Place left at the start and right at the end.
  • Build a set vowels = set("aeiouAEIOU") for O(1) lookup.

Scan:

  • If s[left] is not a vowel, advance left inward - skip it.
  • If s[right] is not a vowel, retreat right inward - skip it.
  • If both are vowels, swap them and then move both pointers inward.
  • Repeat until left >= right.

Result:

  • Join the list back and return. All vowels are now in reversed order; consonants are untouched.
Analysis
Time
O(N)
  • N is the length of the string. Each character is visited at most once by one of the two pointers.
Space
O(N)
  • The string is converted to a mutable list. The vowels set is fixed size (20 characters at most).
FIG. 345 REVERSE VOWELS OF A STRING● INTERACTIVE
visualization loads as you reach it
class Solution:
def reverseVowels(self, s: str) -> str:
left, right = 0, len(s) - 1
s = list(s)
vowels = set("aeiouAEIOU")
while left < right:
if s[left] not in vowels:
left += 1
elif s[right] not in vowels:
right -= 1
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return "".join(s)

917. Reverse Only Letters​

Easy·
Explanation

We want to reverse only the letters in the string, leaving all non-letter characters (digits, punctuation, spaces) exactly where they are. Two converging pointers let us skip over non-letters from both ends and swap only the eligible letter pairs.

Setup:

  • Convert the string to a list for in-place swaps.
  • Place left at the start and right at the end.

Scan:

  • If s[left] is not a letter (isalpha() returns False), advance left inward - skip it.
  • If s[right] is not a letter, retreat right inward - skip it.
  • If both are letters, swap them and move both pointers inward.
  • Repeat until left >= right.

Result:

  • Join the list and return. Letters are in reversed order; all other characters stayed in place.
Analysis
Time
O(N)
  • N is the length of the string. Each character is visited at most once by one of the two pointers.
Space
O(N)
  • The string is converted to a mutable list of characters.
FIG. 917 REVERSE ONLY LETTERS● INTERACTIVE
visualization loads as you reach it
class Solution:
def reverseOnlyLetters(self, s: str) -> str:
left, right = 0, len(s) - 1
s = list(s)
while left < right:
if not s[left].isalpha():
left += 1
elif not s[right].isalpha():
right -= 1
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return "".join(s)

Reverse & Invert (2D)​

832. Flipping an Image​

Easy·
2 Approachesclick to switch
Explanation

Build a fresh res matrix and, for every cell image[i][j], write its inverted value into the mirrored column res[i][n-j-1]. Horizontal flip and bit-invert happen in the same assignment, so no separate pass is needed.

Analysis
Time
O(n^2)
  • Every cell of the n x n image is visited once.
Space
O(n^2)
  • A new n x n result matrix is allocated.
FIG. 832 FLIPPING AN IMAGE NEW MATRIX● INTERACTIVE
visualization loads as you reach it
class Solution:
def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
n = len(image)
res = [[None] * n for _ in range(n)]
for i in range(n):
for j in range(n):
res[i][n - j - 1] = int(not image[i][j])
return res

Rotate - Using Reverse​

189. Rotate Array​

Medium·
Explanation

Rotating an array right by k steps moves the last k elements to the front. The cleanest in-place approach exploits a reversal identity: reversing the whole array and then separately un-reversing the two halves lands every element exactly where it belongs after rotation.

Normalise k:

  • k = k % n handles k >= n - rotating by a multiple of the length is a no-op.

Three reversal steps:

  • Reverse the entire array [0, n-1]. This mirrors all elements but puts the two target groups in the right relative position.
  • Reverse the first segment [0, k-1]. The first k elements (which should be at the front after rotation) are now in the correct order.
  • Reverse the second segment [k, n-1]. The remaining elements are likewise restored to correct order.

Why it works:

  • After the full reverse, positions 0..k-1 hold what was n-k..n-1 (reversed), and k..n-1 holds what was 0..n-k-1 (reversed). Reversing each half separately un-does the unwanted reversal, leaving both groups in their original relative order but in the correct final positions.

reverseSubArray helper:

  • A simple two-pointer swap loop that swaps arr[left] and arr[right] and advances the pointers toward the center. The right boundary is inclusive.
Analysis
Time
O(N)
  • Each of the three reversals touches at most N elements. Total work is proportional to N.
Space
O(1)
  • All swaps happen in-place. Only a single tmp variable is used during each swap.
FIG. 189 ROTATE ARRAY● INTERACTIVE
visualization loads as you reach it
def reverseSubArray(arr, left, right): # right is inclusive
while left < right:
tmp = arr[right]
arr[right] = arr[left]
arr[left] = tmp
left += 1
right -= 1
 
 
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k = k % n
reverseSubArray(nums, 0, n - 1)
reverseSubArray(nums, 0, k - 1)
reverseSubArray(nums, k, n - 1)

Quick Left Rotation​

Basic·
Explanation

Left-rotating an array by k positions moves the first k elements to the end. This is the mirror operation of a right rotation, and the same triple-reversal trick applies - but the two half-reversals target different segments.

Normalise k:

  • k = k % n ensures k stays within [0, n-1], making the algorithm safe for any input.

Three reversal steps:

  • Reverse the entire array [0, n-1]. This sets up both groups in reversed but correctly relative positions.
  • Reverse the first segment [0, n-k-1]. This restores the elements that should appear at the front (originally arr[k:]) to their correct order.
  • Reverse the second segment [n-k, n-1]. This restores the elements that should appear at the back (originally arr[:k]) to their correct order.

Why it differs from right rotation:

  • A left rotation by k is equivalent to a right rotation by n - k. The segment boundaries simply shift: instead of reversing [0, k-1] and [k, n-1], we reverse [0, n-k-1] and [n-k, n-1].

reverseSubArray helper:

  • A two-pointer swap loop - swaps arr[left] and arr[right], then advances the pointers toward the center until they meet.
Analysis
Time
O(N)
  • Three reversal passes collectively visit each element a constant number of times, so total work is O(N).
Space
O(1)
  • Rotation is performed entirely in-place using only a tmp swap variable.
FIG. QUICK LEFT ROTATION● INTERACTIVE
visualization loads as you reach it
def reverseSubArray(arr, left, right): # right is inclusive
while left < right:
tmp = arr[right]
arr[right] = arr[left]
arr[left] = tmp
left += 1
right -= 1
 
 
class Solution:
def leftRotate(self, nums, k, n):
n = len(nums)
k = k % n
reverseSubArray(nums, 0, n - 1)
reverseSubArray(nums, 0, n - k - 1)
reverseSubArray(nums, n - k, n - 1)

Sorted Array​

167. Two Sum II - Input Array Is Sorted​

Medium·
Explanation

The array is already sorted, which gives us a powerful invariant: the smallest sum reachable from any position is at the leftmost element and the largest is at the rightmost. Two pointers starting at opposite ends can home in on the target without revisiting any pair.

Initialise:

  • left = 0, right = len(numbers) - 1. Together they span the entire sorted range.

Converge:

  • At each step, compute total = numbers[left] + numbers[right].
  • If total < target - the current pair is too small. The only way to increase the sum is to move left rightward (to a larger value), because moving right leftward would only decrease it further.
  • If total > target - the pair is too large. Move right leftward to decrease the sum.
  • If total == target - the answer is found. Return 1-indexed positions [left + 1, right + 1].

Why no pair is missed:

  • When we discard left (by advancing it), we've proven that numbers[left] + numbers[right] is too small, and since right is the maximum reachable index, numbers[left] cannot contribute to any valid pair with any remaining right-side element. The symmetric argument holds for discarding right.

The problem guarantees exactly one solution exists, so the loop always terminates before the pointers cross.

Analysis
Time
O(N)
  • Each pointer moves at most N steps in total. At every iteration one pointer advances, so the loop runs at most N - 1 iterations.
Space
O(1)
  • Only two index variables and one running sum are needed, regardless of array length.
FIG. 167 TWO SUM II INPUT ARRAY IS SORTED● INTERACTIVE
visualization loads as you reach it
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total < target:
left += 1
elif total > target:
right -= 1
else:
return [left + 1, right + 1]
return [-1, -1]

Sort the Array​

977. Squares of a Sorted Array​

Easy·
Explanation

The input array is sorted, so the largest absolute values live at either end. After squaring, the largest square must come from one of the two outermost elements. Two pointers starting at opposite ends let us fill the output from the back in one pass, always placing the larger square first.

Initialise:

  • left = 0, right = len(nums) - 1. A helper square = lambda i: nums[i] * nums[i] computes squares without repeating the multiplication expression.

Fill from the back:

  • At each step, compare square(right) and square(left).
  • If square(right) > square(left) - the right end contributes the larger square. Prepend it to ans and move right inward.
  • Otherwise - the left end contributes the larger (or equal) square. Prepend it and move left inward.
  • Inserting at index 0 (ans.insert(0, ...)) naturally builds the result in ascending order.

Why the answer is always sorted:

  • Each inserted value is the current maximum, and we insert at the front. So the sequence of inserted values is non-increasing, making the final list non-decreasing.

The loop ends when left > right, at which point all n squares have been placed exactly once.

Analysis
Time
O(n²)
  • n is the length of nums - the while left <= right loop runs n times, but each ans.insert(0, ...) shifts every existing element over by one, an O(i) operation on the ith insertion. Summed across all n insertions, that is 1 + 2 + ... + n, which is O(n²).
Space
O(n)
  • The output list ans stores n squared values. No other data structures are used.
FIG. 977 SQUARES OF A SORTED ARRAY● INTERACTIVE
visualization loads as you reach it
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
left, right = 0, len(nums) - 1
ans = []
square = lambda i: nums[i] * nums[i]
while left <= right:
if square(right) > square(left):
ans.insert(0, square(right))
right -= 1
else:
ans.insert(0, square(left))
left += 1
return ans

905. Sort Array By Parity​

Easy·
Explanation

We want all even numbers before all odd numbers, in-place. Two pointers - one starting from the left looking for a misplaced odd, one from the right looking for a misplaced even - meet in the middle, swapping mismatched pairs as they go.

Invariant maintained:

  • Everything to the left of left is even.
  • Everything to the right of right is odd.
  • The region between them is unsorted and still to be processed.

Three cases at each step:

  • nums[left] is even - it is already in the correct zone. Advance left.
  • nums[right] is odd - it is already in the correct zone. Retreat right.
  • Both are misplaced (nums[left] is odd, nums[right] is even) - swap them, then advance both pointers. One swap fixes two elements at once.

Termination:

  • When left >= right, the two zones have met and the array is fully partitioned.

The odd-cell highlight marks elements that are currently in the wrong place or still unsorted, making it easy to see which cells need to move.

Analysis
Time
O(N)
  • Each element is visited at most once. Every step advances left, retreats right, or does both - so the total number of steps is bounded by N.
Space
O(1)
  • Partitioning is done in-place. The only extra storage is the two index variables.
FIG. 905 SORT ARRAY BY PARITY● INTERACTIVE
visualization loads as you reach it
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
left, right = 0, len(nums) - 1
while left < right:
if nums[left] % 2 == 0:
left += 1
elif nums[right] % 2 == 1:
right -= 1
else:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums