Definition: What Is Two Pointer Technique?
The Two Pointer Technique uses two pointers (indices) to traverse an array or string, usually from different positions or moving at different speeds. It reduces time complexity from O(n²) to O(n) by avoiding nested loops and processing each element at most once.
Two pointers is efficient because instead of checking all pairs of elements (O(n²)), you use two pointers to eliminate possibilities and find solutions in a single pass (O(n)). The pointers move based on conditions, and each element is visited at most once, making it much faster than brute force approaches.
Common patterns include: opposite ends (left and right pointers move toward each other), fast and slow (both start at beginning, move at different speeds), and sliding window (two pointers define a window that slides). Two pointers is one of the most important techniques for coding interviews.
Key Point: Two pointer technique uses two pointers to traverse an array/string, reducing time complexity from O(n²) to O(n). Pointers move based on conditions, and each element is visited at most once. Common patterns: opposite ends, fast/slow, and sliding window.
What: Understanding Two Pointer Patterns
Two pointer technique has several common patterns:
Real-Life Analogy: Two People Walking Toward Each Other
Two pointers is like two people walking toward each other:
They start at opposite ends and move toward each other
They move based on conditions (e.g., sum too large/small)
They meet in the middle - solution found!
Just like two people meeting, pointers move toward each other until they find the solution.
Opposite Ends (Left & Right)
Two pointers start at opposite ends of array/string and move toward each other. Left pointer starts at beginning, right pointer starts at end. They move based on conditions (sum, comparison, etc.). Common for: finding pairs, palindromes, sorted array problems. Time: O(n).
Example: Find two numbers that sum to target in sorted array
Fast and Slow Pointers
Both pointers start at beginning, but move at different speeds. Fast pointer moves 2 steps, slow pointer moves 1 step. Common for: finding middle of linked list, detecting cycles, removing nth node from end. Time: O(n).
Example: Find middle of linked list, detect cycle in linked list
Sliding Window
Two pointers define a window that slides through the array. Left and right pointers expand/contract the window. Common for: subarray problems, substring problems, longest/shortest subarray. Time: O(n).
Example: Find longest substring with at most k distinct characters
Two Pointer Patterns Visualization
Pattern 1: Opposite Ends
Pointers start at opposite ends, move toward each other
Pattern 2: Fast and Slow
Both start at beginning, fast moves twice as fast
Pattern 3: Sliding Window
Window slides, expanding/contracting based on conditions
Important: Two pointer patterns: opposite ends (left/right move toward each other), fast/slow (different speeds), and sliding window (window expands/contracts). Each pattern solves different problems efficiently with O(n) time complexity.
When: When to Use Two Pointers
Use two pointers in these situations:
Use Two Pointers When:
- Sorted arrays: Find pairs, remove duplicates
- Palindromes: Check if string is palindrome
- Linked lists: Find middle, detect cycle
- Subarray problems: Sliding window technique
- O(n²) to O(n): Optimize nested loops
Avoid Two Pointers When:
- Unsorted arrays: Need sorting first
- Need all pairs: Two pointers finds one solution
- Complex conditions: Hard to determine pointer movement
- Non-linear structure: Two pointers work on arrays/lists
- Need backtracking: Two pointers moves forward only
Common Scenario: Use two pointers for sorted arrays, palindromes, linked lists, subarray problems, and when you can optimize O(n²) to O(n). Avoid two pointers for unsorted arrays, when you need all pairs, or complex conditions.
How To: Use Two Pointers with Examples
Learn to use two pointers with examples:
Example 1: Two Sum (Opposite Ends)
Find two numbers in sorted array that sum to target:
# Find two numbers that sum to target
# Array is sorted: [1, 2, 3, 4, 5, 6], target = 7
def two_sum_sorted(arr, target):
left = 0 # Start at beginning
right = len(arr) - 1 # Start at end
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right] # Found!
elif current_sum < target:
left += 1 # Sum too small, move left pointer right
else:
right -= 1 # Sum too large, move right pointer left
return [] # No solution
# Example usage
arr = [1, 2, 3, 4, 5, 6]
target = 7
result = two_sum_sorted(arr, target)
print(result) # Output: [0, 5] (1 + 6 = 7)
# How it works:
# left=0, right=5: 1+6=7 → Found!
# If sum < target: move left right (need larger sum)
# If sum > target: move right left (need smaller sum)Two Sum Process Visualization
Example 2: Check Palindrome (Opposite Ends)
Check if string is palindrome using two pointers:
# Check if string is palindrome
# "racecar" is palindrome (reads same forwards and backwards)
def is_palindrome(s):
# Remove non-alphanumeric and convert to lowercase
s = ''.join(c.lower() for c in s if c.isalnum())
left = 0
right = len(s) - 1
while left < right:
if s[left] != s[right]:
return False # Not palindrome
left += 1
right -= 1
return True # Is palindrome
# Example usage
print(is_palindrome("racecar")) # Output: True
print(is_palindrome("hello")) # Output: False
# How it works:
# Compare characters at left and right pointers
# If they match, move pointers toward center
# If all match, string is palindromePalindrome Check: "racecar"
Example 3: Find Middle of Linked List (Fast & Slow)
Find middle node using fast and slow pointers:
# Find middle of linked list
# Fast pointer moves 2 steps, slow pointer moves 1 step
# When fast reaches end, slow is at middle
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_middle(head):
slow = head # Slow pointer
fast = head # Fast pointer
# Fast moves 2 steps, slow moves 1 step
while fast and fast.next:
slow = slow.next # Move 1 step
fast = fast.next.next # Move 2 steps
return slow # Slow is at middle
# Example: 1 -> 2 -> 3 -> 4 -> 5
# slow at 1, fast at 1
# slow at 2, fast at 3
# slow at 3, fast at 5 (end)
# Return slow (node 3) - middle!
# How it works:
# Fast pointer reaches end in n/2 steps
# Slow pointer is at middle (n/2 steps)Fast & Slow Pointers: Find Middle
Best Practice: Use opposite ends for sorted arrays and palindromes. Use fast/slow for linked lists (middle, cycle detection). Use sliding window for subarray problems. Two pointers reduces O(n²) to O(n). Make sure pointers move correctly based on conditions.
Why: Why Two Pointers Matters
Two pointers matters for these reasons:
O(n) Time Complexity
Two pointers reduces time complexity from O(n²) to O(n). Instead of nested loops checking all pairs, two pointers processes each element once. This makes algorithms much faster, especially for large inputs. O(n) is optimal for many array/string problems.
Space Efficient
Two pointers uses O(1) extra space (just two pointer variables). No need for extra data structures like hash maps or arrays. This makes two pointers memory-efficient, important for memory-constrained environments or large datasets.
Common Interview Topic
Two pointers is a very common coding interview topic. Interviewers frequently ask about two sum, palindromes, linked list problems, and sliding window. Understanding two pointers is essential for technical interviews and coding challenges.
Versatile Technique
Two pointers works for many problems: arrays, strings, linked lists, and sliding windows. It's a versatile technique that can be adapted to different problem types. Learning two pointers helps solve many coding problems efficiently.
Important: Two pointers matters because it provides O(n) time complexity (better than O(n²)), uses O(1) space, is a common interview topic, and is versatile for many problem types. Two pointers is one of the most important techniques for coding interviews.
Frequently Asked Questions
What is the two pointer technique?
Two pointer technique uses two pointers (indices) to traverse an array or string, usually from different positions or moving at different speeds. It reduces time complexity from O(n²) to O(n) by avoiding nested loops. Common patterns: opposite ends (left and right), same start (fast and slow), or sliding window. Two pointers is efficient and commonly used in coding interviews.
How does two pointer technique work?
Two pointer technique works by: 1) Initialize two pointers at different positions, 2) Move pointers based on condition, 3) Process elements at pointer positions, 4) Continue until pointers meet or condition is met. Pointers move toward each other (opposite ends) or in same direction (fast/slow). Each element is visited at most once, giving O(n) time complexity.
When to use two pointer technique?
Use two pointers for: sorted arrays (find pairs, remove duplicates), palindromes (check if string is palindrome), linked lists (find middle, detect cycle), sliding window (subarray problems), and problems that can be solved with O(n) instead of O(n²). Two pointers is great when you can eliminate possibilities by moving pointers.
What are the types of two pointer techniques?
Types of two pointers: 1) Opposite ends (left and right pointers move toward each other), 2) Fast and slow (both start at beginning, move at different speeds), 3) Sliding window (two pointers define window that slides), 4) Meeting in middle (pointers start at ends, meet in middle). Each type solves different problems efficiently.
What is the time complexity of two pointer technique?
Two pointer technique has O(n) time complexity, where n is the size of the array or string. Each element is visited at most once by the pointers. This is much better than O(n²) brute force approach. Space complexity is O(1) if no extra data structures are used. Two pointers is one of the most efficient techniques for array/string problems.