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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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)

Rotate - Using Reverse​

189. Rotate Array​

Medium·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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·
Solutions:
Visualize
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