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·

125Valid Palindrome

2 Approaches

Filter and Reverse

O(N + 2k) timeO(2k) aux

Left / Right Heads

O(N) timeO(1) aux

class Solution:

def isPalindrome(self, s: str) -> bool:

s = [i.lower() for i in s if i.isalnum()]

return s == s[::-1]

---

Reverse a Subarray

344. Reverse String

Easy·

Reverse an Array

E

344Reverse String

Left / Right Heads

O(N) timeO(1) aux

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·

541Reverse String II

Left / Right Heads

O(N) timeO(N) aux

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·

2000Reverse Prefix of Word

Left / Right Heads

O(N) timeO(N) aux

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·

151Reverse Words in a String

Left / Right Heads

O(7N) timeO(2N) aux

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·

186Reverse Words in a String II

Left / Right Heads

O(2N) timeO(1) aux

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·

557Reverse Words in a String III

Left / Right Heads

O(4N) timeO(N) aux

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·

345Reverse Vowels of a String

Left / Right Heads

O(N) timeO(N) aux

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·

917Reverse Only Letters

Left / Right Heads

O(N) timeO(N) aux

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·

832Flipping an Image

2 Approaches

New Matrix

O(N^2) timeO(1) aux

Left / Right Heads

O(N^2) timeO(1) aux

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·

Rotate Array

M

189Rotate Array

Triple Reverse

O(N) timeO(1) aux

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·

Quick Left Rotation

Triple Reverse

O(N) timeO(1) aux

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·

167Two Sum II - Input Array Is Sorted

3 Approaches · 3 patterns

Converging Pointers

O(N) timeO(1) aux

Lookup Before Insert↗ Hash & Set

O(N) timeO(N) aux

Complement by Bisect↗ Binary Search

O(N log N) timeO(1) aux

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·

977Squares of a Sorted Array

Converging Pointers

O(N²) timeO(1) aux

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·

905Sort Array By Parity

Converging Pointers

O(N) timeO(1) aux

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

---