Two Pointers
Lead of Two Pointers
Two pointers to swap
Below is a template to use two pointers to swap elements of a list s. One pointer p1 starts at the beginning of s and the other pointer p2 starts at the end of s. As long as p1 < p2, we swap the two elements pointed by these two pointers, increase p1 and decrease p2. We keep doing this until p1 >= p2.
1def templateTwoPointersToSwap(s: List[str]) -> None:
2 p1 = 0
3 p2 = len(s) - 1
4 while True:
5 if p1 < p2:
6 s[p1], s[p2] = s[p2], s[p1]
7 p1 += 1
8 p2 -= 1
9 else:
10 break
We can defintely replace while True: with while p1 < p2: and avoid using the if condition. However, we intentionally write the template in such a way to make it consistent with the other templates for two pointers. Some problems that can be solved by this template, as well as their solutions, are as follows.
LeetCode 344. Reverse String (Easy)
Its solution shown below is a very straightforward application of the template.
1class Solution:
2 def reverseString(self, s: List[str]) -> None:
3 p1 = 0
4 p2 = len(s) - 1
5 while True:
6 if p1 < p2:
7 s[p1], s[p2] = s[p2], s[p1]
8 p1 += 1
9 p2 -= 1
10 else:
11 break
LeetCode 7. Reverse Integer (Medium)
We just need to convert an integer to a list of strings. Then the problem is converted to LeetCode 344. Reverse String (Easy).
1class Solution:
2 def reverse(self, x: int) -> int:
3 sign = -1 if x < 0 else 1
4 s = list(str(abs(x)))
5
6 p1 = 0
7 p2 = len(s) - 1
8 while True:
9 if p1 < p2:
10 s[p1], s[p2] = s[p2], s[p1]
11 p1 += 1
12 p2 -= 1
13 else:
14 break
15
16 x = int(''.join(s)) * sign
17 return x if -2 ** 31 <= x <= 2 ** 31 - 1 else 0
LeetCode 31. Next Permutation (Medium)
The idea is to find the “first drop” when traversing from right to left, replace the “first drop” with the smallest element that is greater than it and to its right, and reverse all elements to its right. More specifically, we need 4 steps (take nums = [8, 7, 4, 2, 6, 5, 3, 1] as an example):
Traverse the list from right to left, and stop as soon as we encounter the first drop / decrease (the number 2 at index 3). Let
i1 - 1be its index (i1 - 1 = 3)- If the list
numsis sorted descendingly and we can’t find such a drop, the next permutation is justsorted(nums)
- If the list
Among the elements to the right of
nums[i1 - 1], find the smallest / rightmost element that is greater thannums[i1 - 1](the number 3 at index 6). Leti2 - 1be its index (i2 - 1 = 6)Swap
nums[i1 - 1]andnums[i2 - 1](nums = [8, 7, 4, 3, 6, 5, 2, 1])Reverse all the elements to the right of
nums[i1 - 1]using our template to get the final result (nums = [8, 7, 4, 3, 1, 2, 5, 6])
1class Solution:
2 def nextPermutation(self, nums: List[int]) -> None:
3 """
4 Do not return anything, modify nums in-place instead.
5 """
6 i1 = len(nums) - 1
7 while i1 > 0 and nums[i1 - 1] >= nums[i1]:
8 i1 -= 1
9
10 if i1 == 0:
11 nums.sort()
12 return
13
14 i2 = i1
15 while i2 < len(nums) and nums[i2] > nums[i1 - 1]:
16 i2 += 1
17
18 nums[i1 - 1], nums[i2 - 1] = nums[i2 - 1], nums[i1 - 1]
19
20 p1 = i1
21 p2 = len(nums) - 1
22 while True:
23 if p1 < p2:
24 nums[p1], nums[p2] = nums[p2], nums[p1]
25 p1 += 1
26 p2 -= 1
27 else:
28 break
29
30 return nums
LeetCode 556. Next Greater Element III (Medium)
We just need to convert an integer to a list of digits. Then the problem is converted to LeetCode 31. Next Permutation (Medium).
1class Solution:
2 def nextGreaterElement(self, n: int) -> int:
3 nums = [int(d) for d in str(n)]
4
5 i1 = len(nums) - 1
6 while i1 > 0 and nums[i1 - 1] >= nums[i1]:
7 i1 -= 1
8
9 if i1 == 0:
10 return -1
11
12 i2 = i1
13 while i2 < len(nums) and nums[i2] > nums[i1 - 1]:
14 i2 += 1
15
16 nums[i1 - 1], nums[i2 - 1] = nums[i2 - 1], nums[i1 - 1]
17
18 p1 = i1
19 p2 = len(nums) - 1
20 while True:
21 if p1 < p2:
22 nums[p1], nums[p2] = nums[p2], nums[p1]
23 p1 += 1
24 p2 -= 1
25 else:
26 break
27
28 nums = int(''.join(str(d) for d in nums))
29 return nums if -2 ** 31 <= nums <= 2 ** 31 - 1 else -1
Two pointers to swap after skipping elements
Below is a template to use two pointers to swap elements of a list s after skipping elements that satisfy some conditions.
1def templateTwoPointersToSwapAfterSkippingElems(s: str) -> None:
2 s = list(s)
3
4 p1 = 0
5 p2 = len(s) - 1
6 while True:
7
8 while p1 <= len(s) - 1 and s[p1] satisfies some conditions:
9 p1 += 1
10 while p2 >= 0 and s[p2] satisfies some conditions:
11 p2 -= 1
12
13 if p1 < p2:
14 s[p1], s[p2] = s[p2], s[p1]
15 p1 += 1
16 p2 -= 1
17 else:
18 break
The main difference is that we have two additional while loops in the first while loop to help us skip / ignore some elements (make sure you bear in mind this very commonly used code snippet). Also, never forget the conditions p1 <= len(s) - 1 and p2 >= 0 to avoid the out-of-index error. Some problems that can be solved by this template, as well as their solutions, are as follows.
LeetCode 917. Reverse Only Letters (Easy)
Its solution shown below is a very straightforward application of the template.
1class Solution:
2 def reverseOnlyLetters(self, s: str) -> str:
3 s = list(s)
4
5 p1 = 0
6 p2 = len(s) - 1
7 while True:
8
9 while p1 <= len(s) - 1 and not s[p1].isalpha():
10 p1 += 1
11 while p2 >= 0 and not s[p2].isalpha():
12 p2 -= 1
13
14 if p1 < p2:
15 s[p1], s[p2] = s[p2], s[p1]
16 p1 += 1
17 p2 -= 1
18 else:
19 break
20
21 return ''.join(s)
LeetCode 905. Sort Array By Parity (Easy)
Its solution shown below is a very straightforward application of the template.
1class Solution:
2 def sortArrayByParity(self, s: List[int]) -> List[int]:
3 p1 = 0
4 p2 = len(s) - 1
5 while True:
6
7 while p1 <= len(s) - 1 and s[p1] % 2 == 0:
8 p1 += 1
9 while p2 >= 0 and s[p2] % 2 == 1:
10 p2 -= 1
11
12 if p1 < p2:
13 s[p1], s[p2] = s[p2], s[p1]
14 p1 += 1
15 p2 -= 1
16 else:
17 break
18
19 return s