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:
FIG. 125 VALID PALINDROME● INTERACTIVE
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:
FIG. 344 REVERSE STRING● INTERACTIVE
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:
FIG. 541 REVERSE STRING II● INTERACTIVE
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:
FIG. 2000 REVERSE PREFIX OF WORD● INTERACTIVE
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:
FIG. 151 REVERSE WORDS IN A STRING● INTERACTIVE
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:
FIG. 186 REVERSE WORDS IN A STRING II● INTERACTIVE
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:
FIG. 557 REVERSE WORDS IN A STRING III● INTERACTIVE
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:
FIG. 345 REVERSE VOWELS OF A STRING● INTERACTIVE
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:
FIG. 917 REVERSE ONLY LETTERS● INTERACTIVE
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:
FIG. 189 ROTATE ARRAY● INTERACTIVE
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:
FIG. QUICK LEFT ROTATION● INTERACTIVE
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:
FIG. 167 TWO SUM II INPUT ARRAY IS SORTED● INTERACTIVE
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:
FIG. 977 SQUARES OF A SORTED ARRAY● INTERACTIVE
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:
FIG. 905 SORT ARRAY BY PARITY● INTERACTIVE
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