Pattern 02 of 22
Two Pointers Pattern: Template + 201 LeetCode Problems
Use the order already in the input to discard half the search space at every step.
- Easy
- 58
- Medium
- 118
- Hard
- 25
What the two pointers pattern is
Two pointers walk the input with two indices whose movement is driven by a comparison rather than by a loop counter, and the whole technique rests on one idea: if the input is ordered, the comparison tells you which pointer cannot possibly be part of the answer, so moving it throws away a whole family of candidates at once. In the converging form the pointers start at opposite ends and step inward — for a target sum, a total that is too small can only be fixed by a larger left value, so the left pointer moves and every pair involving the old left value is eliminated in one step. The same-direction form uses a slow write index behind a fast read index and is how in-place filtering and de-duplication are done without extra memory. The fast-and-slow variant advances one pointer twice as fast as the other, which detects a cycle in a linked list and finds its midpoint without knowing the length.
When to use it
- The input is sorted, or sorting it first does not destroy the answer.
- You are looking for a pair, triple, or a partition point rather than a subarray.
- The problem asks for an in-place rewrite in O(1) extra space.
- A linked list needs a midpoint, a cycle check, or the nth node from the end in one pass.
The two pointers template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 201 problems listed below.
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return [left, right]
if total < target:
left += 1 # only a larger left value can reach the target
else:
right -= 1 # only a smaller right value can
return []Complexity characteristics
- Time
- O(n), or O(n log n) when the input has to be sorted first
- Auxiliary space
- O(1)
Each pointer only ever moves in one direction, so between them they take at most n steps and the scan is linear. When the input arrives unsorted the sort dominates and the whole solution is O(n log n) — worth saying out loud, because it is exactly the difference between this and a hash-map solution that stays linear. The extra space is two integers, and the fast-and-slow variant on a linked list is likewise O(1), which is normally the constraint being tested.
Eyes only
Meet the two pointers problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 201 two pointers LeetCode problems
Every problem in the library the two pointers pattern applies to, grouped by LeetCode's own difficulty rating. 169 of the 201 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (58)
Medium (118)
Hard (25)
Two Pointers pattern FAQ
What is the two pointers pattern?
Two pointers walk the input with two indices whose movement is driven by a comparison rather than by a loop counter, and the whole technique rests on one idea: if the input is ordered, the comparison tells you which pointer cannot possibly be part of the answer, so moving it throws away a whole family of candidates at once.
How many LeetCode problems use the two pointers pattern?
This page lists 201 LeetCode problems that the two pointers pattern applies to: 58 Easy, 118 Medium and 25 Hard. 169 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the two pointers pattern?
O(n), or O(n log n) when the input has to be sorted first time and O(1) space. Each pointer only ever moves in one direction, so between them they take at most n steps and the scan is linear. When the input arrives unsorted the sort dominates and the whole solution is O(n log n) — worth saying out loud, because it is exactly the difference between this and a hash-map solution that stays linear. The extra space is two integers, and the fast-and-slow variant on a linked list is likewise O(1), which is normally the constraint being tested.
When should I use the two pointers pattern in an interview?
The input is sorted, or sorting it first does not destroy the answer. You are looking for a pair, triple, or a partition point rather than a subarray.
Which two pointers problem should I start with?
LeetCode 26. Remove Duplicates from Sorted Array is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to two pointers?
Sliding Window, Sorting, Binary Search, Linked List. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.