The two pointer technique is one of the most common and powerful patterns used in competitive programming, data structures, and algorithms. It helps solve problems that involve searching, sorting, or traversing arrays, strings, or linked lists in an efficient way.
Table of Contents
Core
The Two Pointers pattern is a common algorithmic technique used primarily to simplify problems that involve arrays or linked lists. This technique uses two pointers that either move towards each other, away from each other, or in a synchronous manner, to scan the array or list in one or two passes.
At its core, the idea is simple. Instead of brute-forcing through every possible pair (which usually takes O(n²) time), we strategically move two pointers to find solutions in O(n) or O(n log n).
When to Use the Two Pointer Technique
You should consider using two pointers when:
- Sorted arrays or strings are involved: Many problems with sorted data can be solved in linear time with two pointers.
- You need to find a pair or subarray that meets a condition: Examples: target sum, closest pair, longest substring, sliding window problems.
- You want to avoid nested loops: Instead of iterating twice, two pointers can achieve the same result with one pass.
Types of Two Pointer Approaches
Opposite Ends (Converging Pointers)
The first type of problem is having two pointers at the left and right ends of the array, then moving them to the centre while processing something with them.
Template
def converging_pointers(arr):
left = 0
right = len(arr) - 1
while left < right:
# --- process current pair ---
# Example:
# if condition(arr[left], arr[right]):
# do_something()
# left += 1
# right -= 1
# --- move pointers based on logic ---
if should_move_left(arr[left], arr[right]):
left += 1
elif should_move_right(arr[left], arr[right]):
right -= 1
else:
left += 1
right -= 1
Example Problem: Find if a sorted array has two numbers that sum to a target.
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target:
return True
elif s < target:
left += 1
else:
right -= 1
return False- Time Complexity: O(n)
- Space Complexity: O(1)
Same Direction (Sliding Window / Expanding & Contracting)
- Both pointers move forward but at different speeds.
- Often used to maintain a window of elements that satisfy certain conditions.
Example Problem: Longest substring without repeating characters.
def longest_unique_substring(s):
seen = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in seen:
seen.remove(s[left])
left += 1
seen.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
'''
Example
"abcabcbb" → "abc" → length 3
"bbbbb" → "b" → length 1
"pwwkew" → "wke" → length 3
'''- Time Complexity: O(n)
- Space Complexity: O(n)
Fast & Slow Pointers (Tortoise and Hare)
- One pointer moves one step at a time, the other moves faster.
- Useful in linked lists and cycle detection.
Example Problem: Detect if a linked list has a cycle.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
- Time Complexity: O(n)
- Space Complexity: O(1)
Common Problems Solved with Two Pointers
Array Problems
- Two Sum in sorted array
- Trapping Rain Water
- Remove Duplicates from Sorted Array
- Container With Most Water
String Problems
- Longest Substring without Repeating Characters
- Valid Palindrome (check ignoring non-alphanumeric)
- Minimum Window Substring (sliding window variation)
Linked List Problems
- Detect cycle in linked list
- Find middle of a linked list
- Merge two sorted linked lists
Advantages of Two Pointers
- Optimized – Reduces time complexity from O(n²) to O(n).
- Simple & Intuitive – Easy to implement once recognized.
- Versatile – Works with arrays, strings, and linked lists.
Tips to Master the Technique
- Look for sorted input → often a hint.
- Think about reducing brute force → Can we move one pointer instead of looping twice?
- Practice sliding window problems → They are extensions of two pointers.
- Visualize movement → Draw array/string with arrows for clarity.
Practice
Leetcode 167: Two Sum II – Input Array Is Sorted
class Solution:
def twoSum(self, numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1] # 1-indexed
elif current_sum < target:
left += 1
else:
right -= 1class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n - 2):
# skip duplicate fixed element
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, n - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s == 0:
res.append([nums[i], nums[l], nums[r]])
# move both pointers
l += 1
r -= 1
# skip duplicates
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
elif s < 0:
l += 1
else:
r -= 1
return resBy Two pointer
class Solution:
def judgeSquareSum(self, c: int) -> bool:
a = 0
b = int(c ** 0.5)
while a <= b:
s = a*a + b*b
if s == c:
return True
elif s < c:
a += 1
else:
b -= 1
return False
'''
why b = int(c**0.5)
b*b = c-a*a
b = sqrt(c-a*a)
let suppose a = b =sqrt(c)
then a*a+b*b ==> 2c
even if one of a or b is greater than sqrt(c) will in valid a*a+b*b =c
example
b greater than sqrt(c)
a*a + b*b> c , Hence both should be less than sqrt(c)
'''By binary search
class Solution:
def judgeSquareSum(self, c: int) -> bool:
import math
limit = int(math.isqrt(c)) # ⌊√c⌋ safely
for a in range(limit + 1):
target = c - a*a
if self.binary_search(0, limit, target):
return True
return False
def binary_search(self, left: int, right: int, target: int) -> bool:
while left <= right:
mid = (left + right) // 2
sq = mid * mid
if sq == target:
return True
elif sq < target:
left = mid + 1
else:
right = mid - 1
return False
'''
a² + b² = c
⇒ b² = c − a²
Key points:
a ranges from 0 to ⌊√c⌋
For each a, search b in range [0, ⌊√c⌋]
Never take sqrt of negative numbers
'''Two pointers are optimal, but binary search is often asked in interviews.
By Hast set
class Solution:
def judgeSquareSum(self, c: int) -> bool:
squares = set()
i = 0
while i * i <= c:
squares.add(i * i)
i += 1
for s in squares:
if c - s in squares:
return True
return False
| Approach | Time | Space |
|---|---|---|
| Two Pointers | O(√c) | O(1) |
| Binary Search | O(√c log c) | O(1) |
| Hash Set | O(√c) | O(√c) |
Leetcode 125: Valid Palindrome
class Solution:
def isPalindrome(self, s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
# skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
Other Questions
- 344. Reverse String
- 11. Container With Most Water
- 42. Trapping Rain Water
- 3. Longest Substring Without Repeating Characters
- 209. Minimum Size Subarray Sum
- 76. Minimum Window Substring
- 159. Longest Substring with At Most Two Distinct Characters
- 1004. Max Consecutive Ones III
- 141. Linked List Cycle
- 142. Linked List Cycle II
- 876. Middle of the Linked List
- 19. Remove Nth Node From End of List
- 202. Happy Number
- 26. Remove Duplicates from Sorted Array
- 27. Remove Element
- 283. Move Zeroes
- 80. Remove Duplicates from Sorted Array II
- 977. Squares of a Sorted Array
- 16. 3Sum Closest
- 30. Substring with Concatenation of All Words
- 992. Subarrays with K Different Integers
Conclusion
The two pointer technique is a must-know for anyone preparing for coding interviews or competitive programming. From searching pairs in sorted arrays to detecting cycles in linked lists, it significantly simplifies complex problems.