As the name suggests, the two-pointer approach can be used to help process two elements per loop, instead of just one. For the purpose of this article, a pointer is an index of an array.
There are two common scenarios in which the two-pointer approach is used. In one scenario, one pointer starts from the beginning and the other pointer starts from the end, moving toward one another until they both meet. In the other scenario, one pointer moves at a slow speed, while the other pointer moves at a fast speed, both of them moving in the same direction.
Below is a list of practice problems from Leetcode that can be solved using the two-pointer approach. You can acquaint yourself with how this approach is used.
https://leetcode.com/problems/container-with-most-water/
class Solution:
def maxArea(self, height: List[int]) -> int:
max_area = 0
l = 0
r = len(height) - 1
while l < r:
area = (r - l) * min(height[l], height[r])
max_area = max(area, max_area)
if height[l] <= height[r]:
l += 1
else:
r -= 1
return max_area
https://leetcode.com/problems/3sum/
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans = []
nums = sorted(nums)
n = len(nums)
for i in range(0, n - 2):
j = i + 1
k = n - 1
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
while j < k:
total = nums[i] + nums[j] + nums[k]
if total > 0:
k -= 1
elif total < 0:
j += 1
else:
ans.append([nums[i], nums[j], nums[k]])
j += 1
k -= 1
while j < k and nums[j] == nums[j - 1]:
j += 1
while j < k and nums[k] == nums[k + 1]:
k -= 1
return ans
https://leetcode.com/problems/3sum-closest/
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
diff = float("inf")
ans = 0
nums = sorted(nums)
n = len(nums)
for i in range(n - 2):
j = i + 1
k = n - 1
while j < k:
total = nums[i] + nums[j] + nums[k]
if abs(total - target) < diff:
diff = abs(total - target)
ans = total
if total < target:
j += 1
else:
k -= 1
return ans
https://leetcode.com/problems/3sum-smaller/
class Solution:
def threeSumSmaller(self, nums: List[int], target: int) -> int:
ans = 0
nums = sorted(nums)
n = len(nums)
if len(nums) < 3:
return ans
for i in range(n - 2):
j = i + 1
k = n - 1
while j < k:
total = nums[i] + nums[j] + nums[k]
if total < target:
ans += k - j
j += 1
else:
k -= 1
return ans
https://leetcode.com/problems/3sum-with-multiplicity/
class Solution:
def threeSumMulti(self, arr: List[int], target: int) -> int:
ans = 0
mod = 10**9 + 7
lookup = {}
lookup[arr[0] + arr[1]] = 1
for i in range(2, len(arr)):
ans += lookup.get(target - arr[i], 0)
for j in range(i):
lookup[arr[j] + arr[i]] = lookup.get(arr[j] + arr[i], 0) + 1
return ans % mod
https://leetcode.com/problems/valid-triangle-number/
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
ans = 0
nums = sorted(nums)
n = len(nums)
for i in range(n - 1, 1, -1):
l = 0
r = i - 1
while l < r:
if nums[l] + nums[r] > nums[i]:
ans += r - l
r -= 1
else:
l += 1
return ans
https://leetcode.com/problems/4sum/
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
ans = []
nums = sorted(nums)
n = len(nums)
for i in range(0, n - 3):
if nums[i] > target / 4:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
if nums[i] + nums[j] > target / 2:
break
if j > i + 1 and nums[j] == nums[j - 1]:
continue
l = j + 1
r = n - 1
while l < r:
total = nums[i] + nums[j] + nums[l] + nums[r]
if total > target:
r -= 1
elif total < target:
l += 1
else:
ans.append([nums[i], nums[j], nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
return ans
https://leetcode.com/problems/merge-sorted-array/
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
i = m - 1
j = n - 1
k = m + n - 1
while i >= 0 and j >= 0:
if nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
if j >= 0:
nums1[:k + 1] = nums2[:j + 1]
https://leetcode.com/problems/sort-colors/
class Solution:
def sortColors(self, nums: List[int]) -> None:
l = 0
r = len(nums) - 1
i = 0
while i <= r:
if nums[i] == 0:
nums[l], nums[i] = nums[i], nums[l]
l += 1
i += 1
elif nums[i] == 2:
nums[r], nums[i] = nums[i], nums[r]
r -= 1
else:
i += 1
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
slow = 0
n = len(nums)
for fast in range(1, n):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
if n <= 2:
return n
slow = 2
for fast in range(2, n):
if nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slow