Two Pointers: Opposite Ends
Use left and right pointers moving toward each other to solve pair-sum in sorted arrays, valid palindrome, and trapping rain water.
Two Pointers: Opposite Ends is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Two-Pointer Idea
The two-pointer technique uses two index variables that move toward each other (or in the same direction) to reduce the need for nested loops. Instead of checking every pair in O(n²), you make progress with each comparison and finish in O(n). It almost always requires the array to be sorted first, because sorting lets you reason about which direction to move each pointer based on whether the current pair sum is too large or too small.
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []Two-Sum in a Sorted Array
With a sorted array, place one pointer at the left end (smallest) and one at the right end (largest). If the sum is too small, move the left pointer right to increase it. If the sum is too large, move the right pointer left to decrease it. Each iteration advances at least one pointer, so the loop runs at most n times: O(n) total after the sort. Importantly, each move is provably correct because of the sorted ordering.
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]Valid Palindrome Check
A string is a palindrome if it reads the same forwards and backwards. Use two pointers starting at both ends and moving inward: compare characters, skip non-alphanumeric characters, and stop when pointers cross. This runs in O(n) time with O(1) extra space — far cleaner than reversing the string and comparing, which allocates O(n) extra memory.
def is_palindrome(s):
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
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # FalseThree-Sum: Sort + Two Pointers
Three-sum asks for all unique triplets that sum to zero. Sort the array, then fix each element nums[i] and run a two-pointer search in the remaining subarray for a pair summing to -nums[i]. Skip duplicates of both the fixed element and the found pair to avoid repeated triplets. Total time: O(n²) after O(n log n) sort.
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]Container With Most Water
Given heights of vertical lines, find two lines that form a container holding the most water. Area = min(height[left], height[right]) × (right - left). Greedily move the pointer at the shorter line inward: moving the taller one can only decrease width without increasing the height bound. This greedy choice is provably optimal and gives O(n) time.
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49Squaring a Sorted Array
Square each element of a sorted array (which may contain negatives) and return the result in sorted order. Negative squares are large; positive squares are small at the center. Place two pointers at both ends and fill the result array from right to left (largest to smallest). O(n) time and O(n) output space — much better than squaring then sorting in O(n log n).
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Trapping Rain Water
Water trapped at index i equals min(max_left, max_right) - height[i]. Two-pointer approach: maintain max_left and max_right running values. When max_left < max_right, the left side is the bottleneck — process the left pointer. Otherwise process the right. This removes the need for separate left-max and right-max arrays, achieving O(1) extra space.
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6Why the Greedy Pointer Move Works
A common interview follow-up is: why is it safe to discard the smaller pointer? Proof sketch for container-with-most-water: suppose height[left] < height[right]. Every pair (left, j) for j < right gives area ≤ height[left] × (j-left) < height[left] × (right-left) ≤ current area. So no pair starting at 'left' with a right index below 'right' can beat the current area. We safely skip them by advancing left.
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')Minimum Difference Pair in Sorted Array
Find the pair of numbers in a sorted array with the smallest absolute difference. Use two adjacent pointers (not opposite ends) scanning together: |nums[i] - nums[i+1]| for all consecutive pairs. The minimum difference in a sorted array always occurs between adjacent elements (because sorting groups close values together). This is O(n) after sorting.
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1Template for Opposite-Ends Two Pointers
Most opposite-ends two-pointer problems follow the same skeleton. Mastering this template lets you adapt it quickly under time pressure. The key decisions are: (1) what condition advances left, (2) what condition advances right, (3) what constitutes a solution, and (4) how to handle duplicates. Practice encoding these decisions from the problem statement before writing any code.
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return resultCounting Valid Pairs with Two Pointers
Two pointers also count pairs efficiently. For the problem 'count pairs with sum < target' in a sorted array: fix the left pointer and use the right pointer to find the rightmost valid right index. All pairs (left, left+1 to right) are valid — add right - left to the count and advance left. This counts all valid pairs in O(n) rather than O(n²).
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: opposite-ends two pointers replace O(n²) pair enumeration with O(n) left-right convergence on sorted arrays, the decision of which pointer to advance follows from the problem's monotonic property — move the side that currently limits progress, and three-sum, container-with-most-water, trapping rain water, and palindrome verification all reduce to the same core template. Next up we explore slow-and-fast two-pointer patterns.
Frequently asked questions
Is the “Two Pointers: Opposite Ends” lesson free?
Yes — the full text of “Two Pointers: Opposite Ends” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Two Pointers: Opposite Ends”?
Use left and right pointers moving toward each other to solve pair-sum in sorted arrays, valid palindrome, and trapping rain water. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Two Pointers: Opposite Ends” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Array Basics and In-Place Operations
- Prefix Sums and Running Totals
- Two Pointers: Opposite Ends
- Two Pointers: Slow and Fast