Introduction
Imagine you are given an array A, and you want to find some number of pairs of indices where some condition is true. A brute force approach is to consider all O(n²) pairs of indices, and check the condition for each. But, what if due to the structure of the array (ex: sorted), if some condition is true or false, we can discard large parts of the array - significantly improving our time complexity from quadratic to linear?
Correctness must be argued from the fact that, for a fixed i,j: if we move i forward, all pairs (i, k) for k: i < k < j cannot be correct, and similarly if we move j backwards, all pairs for k: (k, j) for j > k > i cannot be correct. This is because we are effectively discarding all these pairs from our search space on every iteration. If this behavior is satisfied, this is what allows us to optimize our solution from O(n²) to O(n).
Two Pointers Template
Two Pointers is where we initiate two pointers, i,j - to 0 and len(A)-1, the first and last indices of the array.
The idea is that by comparing A[i] and A[j], we can make a decision to either move i forward, or j backwards.
O(n), because we move i at most n times forwards and j at most n times backwards, and every iteration we move either i or j once.
O(1), since we are just maintaining some integer pointers.
O(n)O(1)General Template
Initialize pointers at opposite ends of the array. Move one pointer based on the condition.
def f(self, A: List[int]) -> int:
n = len(A)
i = 0
j = n - 1
res = 0 # updated somehow during iteration
while i < j:
if condition(A[i], A[j]):
j -= 1
else:
i += 1
return resTwo Sum Variants
Classic two pointer problems involving finding pairs that satisfy some sum condition.
01Two Sum II - Input Array Is SortedMedium
Given a sorted (ascending) array A and target T, find two indices [i,j], i < j where A[i] + A[j] = T.
def twoSum(self, A: List[int], T: int) -> List[int]:
i, j = 0, len(A) - 1
while i < j:
if A[i] + A[j] == T:
return [i + 1, j + 1]
elif A[i] + A[j] > T:
j -= 1
else:
i += 1
return [-1, -1]O(n)O(1)Why does this work?
If A[i] + A[j] is too big (> T), we must decrement j to reduce the sum, because incrementing i will increase the sum (A is sorted).
Similarly, if A[i] + A[j] is too small (< T), we must increment i to increase the sum, because decrementing j will decrease the sum.
When we move i forward with A[i] + A[j] < T, all pairs (i, k) for k: i < k < j have sum clearly even smaller than A[i] + A[j] < T, since A[k] < A[j], so we can safely discard them.
02Two Sum Less Than KEasy
Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k.
def twoSumLessThanK(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
res = -1
i, j = 0, n - 1
while i < j:
if nums[i] + nums[j] >= k:
j -= 1
else:
res = max(res, nums[i] + nums[j])
i += 1
return resO(n log n)O(1)We want the largest pair sum that is still less than k (closest to k, from below).
If nums[i] + nums[j] >= k we are clearly too large, so decrement j. If nums[i] + nums[j] < k, we satisfy the condition, but we want to increment i to increase the sum and see if we can get even closer to k without exceeding. There is no point in decrementing j, because our current answer is at least as good.
Three Sum / Triplet Problems
For triplets and beyond (say, size N), the general idea is to fix a value, and then run your algorithm for size N-1. For triplets (i,j,k), we can fix index i and perform two pointers for j,k.
Time complexity: O(n^(N-1))
Space complexity: O(1)
Given we brute force over all indices i, and use two pointers on the remaining indices - correctness follows from the correctness of two pointers. Inductively, correctness follows for N > 3.
01Valid Triangle NumberMedium
Given an array of integers, return the number of all triplets where they can form the edges of a triangle.
def triangleNumber(self, nums: List[int]) -> int:
n = len(nums)
res = 0
nums.sort()
for k in range(n):
i = 0
j = k - 1
while i < j:
if nums[i] + nums[j] > nums[k]:
res += j - i
j -= 1
else:
i += 1
return resO(n²)O(1)We invoke the triangle inequality: in a triangle, any two sides have sum greater than the third, i.e., a + b > c for any 3 sides. This is strongest when c is the largest side.
Fix the largest side c at index k. Now count all pairs (i,j) s.t A[i] + A[j] > c, where i < j < k.
If nums[i] + nums[j] > nums[k], this is valid. Given (i,j), all pairs (m, j) for m: i <= m < j have sum > nums[k] because nums is sorted. So we increment res by j-i, then decrement j since we've counted all valid subarrays ending at j.
023Sum SmallerMedium
Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
def threeSumSmaller(self, nums: List[int], target: int) -> int:
n = len(nums)
nums.sort()
res = 0
for i in range(n):
j = i + 1
k = n - 1
while j < k:
if nums[j] + nums[k] < target - nums[i]:
res += (k - j)
j += 1
else:
k -= 1
return resO(n²)O(1)Rearrange the equation: nums[j] + nums[k] < target - nums[i]. Let c = target - nums[i]. Now for a fixed i, use two pointers to count all (j,k) for i < j < k where nums[j] + nums[k] < c.
Similar to Valid Triangle Number but we're fixing i and finding all (j,k), and counting nums[j] + nums[k] < c rather than > c.
033Sum ClosestMedium
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
nums.sort()
res = inf
for i in range(n):
j = i + 1
k = n - 1
while j < k:
if abs(nums[i] + nums[j] + nums[k] - target) < abs(res - target):
res = nums[i] + nums[j] + nums[k]
if nums[j] + nums[k] < target - nums[i]:
j += 1
else:
k -= 1
return resO(n²)O(1)A combination of the previous 3 Sum problems. We want the closest triplet sum to target (from below OR above).
The subtle difference is that we update res whenever the current triplet sum is closer to target than our best so far. We discard pairs with a sum further from the target than our current sum.
043SumMedium
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
def twoSum(start, end, target):
pairs = []
i, j = start, end
while i < j:
if nums[i] + nums[j] == target:
pairs.append([nums[i], nums[j]])
while i + 1 < j and nums[i] == nums[i + 1]: # skip dups
i += 1
while j - 1 > i and nums[j] == nums[j - 1]: # skip dups
j -= 1
i += 1
j -= 1
elif nums[i] + nums[j] > target:
j -= 1
else:
i += 1
return pairs
i = 0
while i < n:
pairs = twoSum(0, i - 1, -nums[i])
for p in pairs:
res.append(p + [nums[i]])
while i + 1 < n and nums[i] == nums[i + 1]: # skip dups
i += 1
i += 1
return resO(n²)O(1)The classic problem similar to Two Sum. The trick is handling duplicates - we don't want any duplicates in output.
For two sum: if nums[i] + nums[j] == target, append to res, then skip all consecutive nums[i] on the left and all consecutive nums[j] on the right. For a given (i,j) that sums to target, there is no other possible matching value for index i other than nums[j].
Same Direction Two Pointers
Another form of two pointers where both pointers start at the beginning and move in the same direction.
01Maximize Greatness of an ArrayMedium
You are given a 0-indexed integer array nums. You are allowed to permute nums into a new array perm of your choosing.
We define the greatness of nums be the number of indices 0 <= i < nums.length for which perm[i] > nums[i].
Return the maximum possible greatness you can achieve after permuting nums.
def maximizeGreatness(self, nums: List[int]) -> int:
nums.sort()
i, j = 0, 0
n = len(nums)
while j < n:
while j < n and nums[i] == nums[j]:
j += 1
# match nums[i] and nums[j]
if j < n:
i += 1
j += 1
return iO(n log n)O(1)Instead of initializing both pointers at opposite ends, we initialize both at the beginning.
The idea is greedy - for every value v, the optimal permutation has the smallest greater value than v in the same index. Sort the array and keep pointer j representing the immediately next greater value than nums[i] in sorted order.
Edge case: when j == n (no larger value), we only match (i,j) when j < n. The final index of i is precisely the number of matched pairs.
02Divide Players Into Teams of Equal SkillMedium
You are given a positive integer array skill of even length n where skill[i] denotes the skill of the ith player. Divide the players into n / 2 teams of size 2 such that the total skill of each team is equal.
Return the sum of the chemistry of all the teams, or return -1 if there is no way to divide the players.
The chemistry of a team is equal to the product of the skills of the players on that team.
def dividePlayers(self, skill: List[int]) -> int:
skill.sort()
n = len(skill)
target = skill[0] + skill[-1]
chemistry = 0
i, j = 0, n - 1
while i < j:
if skill[i] + skill[j] != target:
return -1
chemistry += skill[i] * skill[j]
i += 1
j -= 1
return chemistryO(n log n)O(1)Classic two pointers from opposite ends. After sorting, pair the smallest with the largest. All pairs must have the same sum (target = skill[0] + skill[-1]). If any pair doesn't match the target, return -1.
Summary
Two Pointers is a foundational technique that is useful in many situations. Mastering it is crucial to becoming a strong leetcoder.
Key Patterns:
1. Opposite ends: Initialize i=0, j=n-1 for pair finding in sorted arrays
2. Same direction: Both pointers start at 0 for matching/greedy problems
3. Triplets: Fix one index, run two pointers on remaining indices
4. Duplicate handling: Use while loops to skip consecutive equal values
When to use Two Pointers:
- Array is sorted (or can be sorted)
- Looking for pairs/triplets satisfying some condition
- Can prove that moving a pointer discards only invalid candidates