Data Structures & AlgorithmsTwo-Pointer Technique

The Two-Pointer Technique

LevelIntermediate

Duration60 mins

TopicTwo-Pointer Technique

5 / 5

When Two-Pointer Applies and When It Doesn't

The Art of Pattern Recognition

Knowing how to implement a two-pointer solution is only half the battle. The other half—arguably the more valuable half—is knowing when to use it.

Pattern recognition is the skill that separates experienced engineers from beginners. An expert sees a problem and immediately thinks "this is a two-pointer problem" or "this won't work with two-pointer, I need dynamic programming." A beginner wastes time trying approaches that don't fit.

This page teaches you to recognize:

Definite indicators that two-pointer will work
Red flags that suggest a different approach
Borderline cases where two-pointer might work with modifications
Alternative techniques when two-pointer doesn't apply

What You Will Learn

By the end of this page, you'll have a mental checklist for evaluating whether two-pointer applies to a given problem. This pattern recognition ability accelerates your problem-solving significantly.

Prerequisites for Two-Pointer

Two-pointer is not a universal technique. It requires specific structural properties in the problem. Let's enumerate these prerequisites clearly.

Core Prerequisites

•Sequential/Linear Data Structure — Arrays, strings, linked lists. Two-pointer doesn't directly apply to trees, graphs, or hash maps (though it may be used as a subroutine).
•Ordered or Sortable Data — For converging pointers, the data must be ordered such that pointer movement direction is meaningful. For same-direction pointers, ordering may not be required.
•Monotonic Relationship — Moving a pointer should have a predictable effect on the quantity being optimized. E.g., in sorted arrays, moving left increases sums, moving right decreases them.
•Pointer Movement Eliminates Candidates — Each step must rule out multiple possibilities, not just one. If you can only eliminate one candidate per move, two-pointer doesn't help.
•No Need to Revisit — Once a pointer moves past an element, you shouldn't need to reconsider it. If backtracking is required, consider different approaches.

The Monotonicity Principle:

This is the most important prerequisite. Two-pointer works when:

Moving one pointer in a direction consistently increases or decreases some target metric.

For example, in a sorted array searching for a pair sum:

Moving left right → increases the sum (sorted property)
Moving right left → decreases the sum (sorted property)

This monotonicity lets you make informed decisions about which pointer to move based on whether the current sum is too large or too small.

When Monotonicity Breaks

If the array is unsorted, moving left or right has unpredictable effects on the sum. You might move left right and get a smaller sum (if a large value is replaced by a small one). Without monotonicity, converging two-pointer doesn't work.

Definite Indicators: When Two-Pointer Works

Some problem patterns almost always indicate a two-pointer solution. Learn to recognize these signals:

Strong Indicators for Two-Pointer
Signal	Example Problem	Pointer Type
"Sorted array" mentioned	Two Sum II	Converging
"In-place" modification required	Remove Duplicates	Same-direction
"O(1) space" constraint	Move Zeroes	Same-direction
"Find pair/triple satisfying X"	3Sum	Converging
"Palindrome" check	Valid Palindrome	Converging
"Container/Area" optimization	Container With Most Water	Converging
"Cycle detection" in sequence	Linked List Cycle	Fast-slow
"Partition" or "segregate"	Sort Colors	Same-direction
"Merge two sorted X"	Merge Sorted Arrays	Two pointers, one per array

Signal: "Find two elements that satisfy a condition in sorted array"

This is the classic indicator. When you see:

Sorted input
Finding a pair (or triple)
Sum/difference/product condition

Immediately think: converging two-pointer.

Signal: "Modify array in-place with O(1) space"

When you need to:

Remove elements
Shift/move elements
Overwrite elements during traversal

Think: same-direction two-pointer with reader/writer positions.

Signal: "Check symmetry"

Palindrome, mirrored structure, comparing ends:

Start at both ends
Move toward center
Compare as you go

indicator_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# SIGNAL: "sorted array" + "find pair"
# Immediate thought: converging two-pointer
 
# Example: Find pair with difference = k
def find_pair_with_difference(arr: list[int], k: int) -> tuple[int, int] | None:
    """
    In sorted array, find pair with difference = k.
    
    Approach: Start both pointers at 0, not opposite ends.
    If difference < k, advance right (increase difference).
    If difference > k, advance left (decrease difference).
    """
    arr.sort()
    left = 0
    right = 1
    
    while right < len(arr):
        diff = arr[right] - arr[left]
        
        if diff == k and left != right:
            return (arr[left], arr[right])
        elif diff < k:
            right += 1
        else:
            left += 1
            if left == right:
                right += 1
    
    return None
 
 
# SIGNAL: "in-place" + "O(1) space"
# Immediate thought: same-direction reader/writer
 
# Example: Remove elements in-place
def remove_value(nums: list[int], val: int) -> int:
    writer = 0
    for reader in range(len(nums)):
        if nums[reader] != val:
            nums[writer] = nums[reader]
            writer += 1
    return writer
 
 
# SIGNAL: "check if X is palindrome"
# Immediate thought: converging from both ends
 
# Example: Check if array is palindromic
def is_palindromic_array(arr: list[int]) -> bool:
    left, right = 0, len(arr) - 1
    while left < right:
        if arr[left] != arr[right]:
            return False
        left += 1
        right -= 1
    return True

Red Flags: When Two-Pointer Doesn't Work

Equally important is recognizing when two-pointer is the wrong approach. Here are red flags:

Red Flags Against Two-Pointer

•Optimal Substructure + Overlapping Subproblems — These signal dynamic programming, not two-pointer. E.g., "minimum cost path" or "count ways to reach target".
•Unsorted data with no clear ordering strategy — If you can't define a meaningful pointer movement direction, two-pointer won't help.
•Need to consider all subsets/combinations — Two-pointer processes elements linearly. If you need exponential exploration, use backtracking.
•Non-linear structures — Trees, graphs, matrices with arbitrary traversal patterns require different techniques.
•Backtracking required — If you might need to revisit a discarded element based on later information, two-pointer's one-way nature doesn't fit.
•Global optimization without greedy property — Two-pointer makes locally optimal moves. If the problem lacks a greedy structure, it may fail.

Example: Longest Increasing Subsequence (LIS)

Can we solve LIS with two-pointer? Let's analyze:

Input is an array ✓
We're looking for a subsequence (not contiguous) ✗
Elements don't need to be adjacent ✗
The problem has optimal substructure (LIS is built from smaller LIS)

Two-pointer fails because:

Moving pointers doesn't tell us about the best subsequence
We need to consider elements in the middle, not just ends
The problem has overlapping subproblems → dynamic programming is correct

Example: Subarray with Given Sum (Unsorted)

For positive-only arrays, sliding window (a form of two-pointer) works. For arrays with negatives... it doesn't! Why?

Adding an element might increase OR decrease the sum
No monotonicity → can't decide pointer direction
Use prefix sums + hash map instead

red_flag_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# RED FLAG: Longest Increasing Subsequence
# Two-pointer CANNOT solve this efficiently
 
# Wrong approach: trying two-pointer
def lis_two_pointer_wrong(nums):
    # This doesn't work! Two-pointer can't find optimal subsequence
    # because LIS elements may not be at the ends
    pass
 
# Correct approach: Dynamic Programming O(n^2) or O(n log n)
def lis_correct(nums: list[int]) -> int:
    if not nums:
        return 0
    
    dp = [1] * len(nums)  # dp[i] = LIS ending at index i
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)
 
 
# RED FLAG: Subarray sum with negatives
# Two-pointer/sliding window fails due to lack of monotonicity
 
# For positive-only: sliding window works
def subarray_sum_positive(nums: list[int], target: int) -> list[int]:
    """Works for positive-only arrays."""
    left = 0
    current_sum = 0
    
    for right in range(len(nums)):
        current_sum += nums[right]
        
        while current_sum > target and left <= right:
            current_sum -= nums[left]
            left += 1
        
        if current_sum == target:
            return [left, right]
    
    return []
 
# For arrays with negatives: need different approach
def subarray_sum_any(nums: list[int], target: int) -> list[int]:
    """Works for any array using prefix sums."""
    prefix_sum = 0
    seen = {0: -1}  # prefix_sum -> index
    
    for i, num in enumerate(nums):
        prefix_sum += num
        
        if prefix_sum - target in seen:
            return [seen[prefix_sum - target] + 1, i]
        
        seen[prefix_sum] = i
    
    return []
 
 
# Example where two-pointer fails:
# nums = [1, -2, 3, -1, 2], target = 3
# Subarray [3] or [1, -2, 3, -1, 2] both sum to 3 or 3
# But sliding window would fail because adding -2 decreases sum
# then adding 3 increases it - no monotonicity!

The Monotonicity Test

Ask yourself: 'If I move the left pointer right, does the target metric always increase (or always decrease)? Same for the right pointer moving left.' If the answer is 'it depends' or 'sometimes yes, sometimes no', two-pointer likely won't work.

Borderline Cases: When Two-Pointer Might Work

Some problems aren't obviously two-pointer, but can be transformed into two-pointer problems with the right insight:

Borderline Scenarios

•Unsorted array → Sort first — If the problem allows O(n log n) time and order doesn't need to be preserved, sort and apply converging pointers.
•Subarray problems with positive numbers — These become sliding window problems, which are a form of same-direction two-pointer.
•Problems requiring index tracking — Map elements to indices, sort by value, then use two-pointer on the value order.
•Two arrays problems — One pointer per array, advancing based on comparisons.
•Circular array — Can sometimes be linearized by doubling the array or handling wraparound.

Case Study: Two Sum (Unsorted)

The classic Two Sum problem with an unsorted array:

Option 1: Sort + Two-Pointer

Sort the array (but lose original indices)
Store (value, original_index) pairs, sort by value
Use converging two-pointer
Time: O(n log n), Space: O(n)

Option 2: Hash Map

Store seen values and their indices
For each element, check if (target - element) is in the map
Time: O(n), Space: O(n)

For unsorted Two Sum, the hash map approach is often better (linear time). But if you need k-sum or the data is already sorted, two-pointer shines.

borderline_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# BORDERLINE: Two Sum on unsorted array
# Can be solved with two-pointer after sorting
 
def two_sum_with_indices(nums: list[int], target: int) -> list[int]:
    """
    Two Sum returning original indices, using sort + two-pointer.
    
    Time: O(n log n)
    Space: O(n) for storing index pairs
    """
    # Store (value, original_index) pairs
    indexed = [(val, idx) for idx, val in enumerate(nums)]
    indexed.sort(key=lambda x: x[0])  # Sort by value
    
    left, right = 0, len(indexed) - 1
    
    while left < right:
        current_sum = indexed[left][0] + indexed[right][0]
        
        if current_sum == target:
            return [indexed[left][1], indexed[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []
 
 
# BORDERLINE: Subarray with maximum sum of length k
# This is sliding window (same-direction two-pointer)
 
def max_sum_subarray_k(nums: list[int], k: int) -> int:
    """
    Find max sum of subarray of length exactly k.
    
    Sliding window: maintain window of size k.
    Time: O(n)
    Space: O(1)
    """
    if len(nums) < k:
        return 0
    
    # Initialize with first window
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    # Slide window
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # Add new, remove old
        max_sum = max(max_sum, window_sum)
    
    return max_sum
 
 
# BORDERLINE: Two arrays, find pair closest to target
def two_array_closest_pair(arr1: list[int], arr2: list[int], target: int) -> tuple:
    """
    Find one element from each array such that their sum is closest to target.
    
    Approach: Sort both, use converging-like logic.
    """
    arr1.sort()
    arr2.sort()
    
    i = 0
    j = len(arr2) - 1
    closest = float('inf')
    best_pair = (arr1[0], arr2[0])
    
    while i < len(arr1) and j >= 0:
        current_sum = arr1[i] + arr2[j]
        
        if abs(current_sum - target) < abs(closest - target):
            closest = current_sum
            best_pair = (arr1[i], arr2[j])
        
        if current_sum < target:
            i += 1
        elif current_sum > target:
            j -= 1
        else:
            return best_pair  # Exact match
    
    return best_pair
 
 
# Test
print(two_sum_with_indices([3, 2, 4], 6))  # [1, 2] (2 + 4 = 6)
print(max_sum_subarray_k([1, 4, 2, 10, 2, 3, 1, 0, 20], 4))  # 24 (10+2+3+1=16? Let's see... 2+3+1+0=6, 3+1+0+20=24)
print(two_array_closest_pair([1, 4, 5, 7], [10, 20, 30, 40], 32))  # (7, 30) sum=37 or (4, 30) sum=34

Alternative Techniques When Two-Pointer Fails

When two-pointer doesn't apply, here are the common alternatives and when to use each:

Alternative Techniques and When to Use Them
Technique	When to Use	Example Problems
Hash Map/Set	Need O(1) lookups, unsorted data, counting	Two Sum, subarray sum with negatives
Dynamic Programming	Optimal substructure + overlapping subproblems	LIS, edit distance, coin change
Binary Search	Sorted data, looking for specific element	Search in rotated array, peak finding
Sliding Window	Contiguous subarray/substring optimization	Max sum subarray of size k
Stack	Matching pairs, next greater element, parentheses	Valid parentheses, daily temperatures
Prefix Sum	Range sum queries, subarray sums	Subarray sum equals k
Divide and Conquer	Problem splits into independent subproblems	Merge sort, closest pair of points
Backtracking	Need to explore all possibilities	Permutations, combinations, N-queens

Decision Flowchart:

Is the data sorted or can you sort it?
├─ YES → Is it a pair/triple finding problem?
│         ├─ YES → Use CONVERGING TWO-POINTER
│         └─ NO → Is it searching for a specific value?
│                  ├─ YES → Use BINARY SEARCH
│                  └─ NO → Consider SLIDING WINDOW or other
│
└─ NO → Need O(1) lookups or counting?
         ├─ YES → Use HASH MAP/SET
         └─ NO → Does problem have optimal substructure?
                  ├─ YES → Use DYNAMIC PROGRAMMING
                  └─ NO → Need to explore all possibilities?
                           ├─ YES → Use BACKTRACKING
                           └─ NO → Analyze further...

Multiple Techniques Combined

Many problems combine techniques. For example, 3Sum uses a loop (fix one element) + two-pointer (find pairs). Four Sum uses two loops + two-pointer. Binary search + two-pointer appears in problems like 'find k closest elements'. Don't limit yourself to one technique per problem.

The Two-Pointer Decision Checklist

When you encounter a new problem, run through this checklist:

Step-by-Step Evaluation

•Is it an array/string/linked list problem? If not (tree, graph, etc.), two-pointer likely doesn't apply directly.
•Is the data sorted or can you sort it without losing information? If yes, converging two-pointer becomes viable.
•Is there a monotonic relationship? Moving a pointer should predictably increase/decrease some target metric.
•Are you looking for pairs, checking symmetry, or doing in-place modification? These are classic two-pointer scenarios.
•Can you make progress without backtracking? Two-pointer moves forward only. If you might need to reconsider earlier elements based on later ones, consider DP or backtracking.
•Is O(n) time and O(1) space achievable and required? Two-pointer often provides this. If O(n) time with O(n) space is acceptable, hash maps might be simpler.

Quick Heuristics:

If you see...	Think...
"Sorted array"	Converging two-pointer
"In-place"	Same-direction reader/writer
"Find pair/triple"	Two-pointer or hash map
"Palindrome"	Converging from both ends
"O(1) space"	Two-pointer or careful in-place
"Cycle in list"	Fast-slow pointers
"Merge sorted"	One pointer per array
"Partition/segregate"	Same-direction swap pointer

Practice Problems Categorized

To solidify pattern recognition, here are problems categorized by technique:

Converging Two-Pointer Problems
Problem	Difficulty	Key Insight
Two Sum II (sorted)	Easy	Classic converging sum search
3Sum	Medium	Fix one + two-pointer for pairs
Container With Most Water	Medium	Move shorter wall inward
Valid Palindrome	Easy	Compare from both ends
Trapping Rain Water	Hard	Two-pointer with max tracking
4Sum	Medium	Two loops + two-pointer

Same-Direction Two-Pointer Problems
Problem	Difficulty	Key Insight
Remove Duplicates from Sorted Array	Easy	Reader-writer paradigm
Remove Element	Easy	Skip unwanted values
Move Zeroes	Easy	Swap non-zeros forward
Sort Colors	Medium	Dutch National Flag, 3 pointers
Partition List (linked list)	Medium	Two separate lists merged

Fast-Slow Pointer Problems
Problem	Difficulty	Key Insight
Linked List Cycle	Easy	Floyd's cycle detection
Linked List Cycle II (find start)	Medium	Two-phase: detect + find start
Find the Duplicate Number	Medium	Array as linked list
Middle of the Linked List	Easy	Fast reaches end, slow is middle
Happy Number	Easy	Sequence forms cycle or terminates

NOT Two-Pointer (Common Confusions)
Problem	Correct Approach	Why Not Two-Pointer
Longest Increasing Subsequence	DP or binary search	Non-contiguous, needs optimal substructure
Subarray Sum (with negatives)	Hash map + prefix sum	No monotonicity
Minimum Window Substring	Sliding window + hash map	Need tracking structure, not pure two-pointer
Edit Distance	Dynamic programming	2D optimization problem

Summary: Pattern Recognition Mastery

You now have a comprehensive framework for recognizing when two-pointer applies. Let's consolidate:

Key Decision Points

•Monotonicity is key — If pointer movement doesn't have a predictable effect on your target metric, two-pointer won't work.
•Keywords trigger patterns — 'Sorted array', 'in-place', 'O(1) space', 'palindrome', 'cycle' all suggest two-pointer variants.
•Red flags mean pivot — Optimal substructure, backtracking need, no monotonicity → consider DP, hash maps, or other techniques.
•Transformation enables technique — Unsorted data can sometimes be sorted. Index tracking can add the information you need.
•Combined techniques are common — Many problems use loop + two-pointer, binary search + two-pointer, or hash map + two-pointer.

The Master Heuristic:

Two-pointer works when you can guarantee that each pointer movement eliminates many candidates from consideration, and you never need to revisit eliminated candidates.

If both conditions hold, two-pointer likely applies. If either fails, look elsewhere.

Module Complete

Congratulations! You've completed the Two-Pointer Technique module. You now understand both variants (same-direction and converging), can implement classic problems, and—most importantly—know when to apply this technique and when to reach for alternatives. This pattern recognition skill will accelerate your problem-solving throughout your career.

5 / 5

Loading learning content...

Data Structures & AlgorithmsTwo-Pointer Technique

The Two-Pointer Technique

LevelIntermediate

Duration60 mins

TopicTwo-Pointer Technique

5 / 5

When Two-Pointer Applies and When It Doesn't

The Art of Pattern Recognition

Knowing how to implement a two-pointer solution is only half the battle. The other half—arguably the more valuable half—is knowing when to use it.

This page teaches you to recognize:

Definite indicators that two-pointer will work
Red flags that suggest a different approach
Borderline cases where two-pointer might work with modifications
Alternative techniques when two-pointer doesn't apply

What You Will Learn

By the end of this page, you'll have a mental checklist for evaluating whether two-pointer applies to a given problem. This pattern recognition ability accelerates your problem-solving significantly.

Prerequisites for Two-Pointer

Two-pointer is not a universal technique. It requires specific structural properties in the problem. Let's enumerate these prerequisites clearly.

Core Prerequisites

•Sequential/Linear Data Structure — Arrays, strings, linked lists. Two-pointer doesn't directly apply to trees, graphs, or hash maps (though it may be used as a subroutine).
•Ordered or Sortable Data — For converging pointers, the data must be ordered such that pointer movement direction is meaningful. For same-direction pointers, ordering may not be required.
•Monotonic Relationship — Moving a pointer should have a predictable effect on the quantity being optimized. E.g., in sorted arrays, moving left increases sums, moving right decreases them.
•Pointer Movement Eliminates Candidates — Each step must rule out multiple possibilities, not just one. If you can only eliminate one candidate per move, two-pointer doesn't help.
•No Need to Revisit — Once a pointer moves past an element, you shouldn't need to reconsider it. If backtracking is required, consider different approaches.

The Monotonicity Principle:

This is the most important prerequisite. Two-pointer works when:

Moving one pointer in a direction consistently increases or decreases some target metric.

For example, in a sorted array searching for a pair sum:

Moving left right → increases the sum (sorted property)
Moving right left → decreases the sum (sorted property)

This monotonicity lets you make informed decisions about which pointer to move based on whether the current sum is too large or too small.

When Monotonicity Breaks

Definite Indicators: When Two-Pointer Works

Some problem patterns almost always indicate a two-pointer solution. Learn to recognize these signals:

Strong Indicators for Two-Pointer
Signal	Example Problem	Pointer Type
"Sorted array" mentioned	Two Sum II	Converging
"In-place" modification required	Remove Duplicates	Same-direction
"O(1) space" constraint	Move Zeroes	Same-direction
"Find pair/triple satisfying X"	3Sum	Converging
"Palindrome" check	Valid Palindrome	Converging
"Container/Area" optimization	Container With Most Water	Converging
"Cycle detection" in sequence	Linked List Cycle	Fast-slow
"Partition" or "segregate"	Sort Colors	Same-direction
"Merge two sorted X"	Merge Sorted Arrays	Two pointers, one per array

Signal: "Find two elements that satisfy a condition in sorted array"

This is the classic indicator. When you see:

Sorted input
Finding a pair (or triple)
Sum/difference/product condition

Immediately think: converging two-pointer.

Signal: "Modify array in-place with O(1) space"

When you need to:

Remove elements
Shift/move elements
Overwrite elements during traversal

Think: same-direction two-pointer with reader/writer positions.

Signal: "Check symmetry"

Palindrome, mirrored structure, comparing ends:

Start at both ends
Move toward center
Compare as you go

indicator_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# SIGNAL: "sorted array" + "find pair"
# Immediate thought: converging two-pointer
 
# Example: Find pair with difference = k
def find_pair_with_difference(arr: list[int], k: int) -> tuple[int, int] | None:
    """
    In sorted array, find pair with difference = k.
    
    Approach: Start both pointers at 0, not opposite ends.
    If difference < k, advance right (increase difference).
    If difference > k, advance left (decrease difference).
    """
    arr.sort()
    left = 0
    right = 1
    
    while right < len(arr):
        diff = arr[right] - arr[left]
        
        if diff == k and left != right:
            return (arr[left], arr[right])
        elif diff < k:
            right += 1
        else:
            left += 1
            if left == right:
                right += 1
    
    return None
 
 
# SIGNAL: "in-place" + "O(1) space"
# Immediate thought: same-direction reader/writer
 
# Example: Remove elements in-place
def remove_value(nums: list[int], val: int) -> int:
    writer = 0
    for reader in range(len(nums)):
        if nums[reader] != val:
            nums[writer] = nums[reader]
            writer += 1
    return writer
 
 
# SIGNAL: "check if X is palindrome"
# Immediate thought: converging from both ends
 
# Example: Check if array is palindromic
def is_palindromic_array(arr: list[int]) -> bool:
    left, right = 0, len(arr) - 1
    while left < right:
        if arr[left] != arr[right]:
            return False
        left += 1
        right -= 1
    return True

Red Flags: When Two-Pointer Doesn't Work

Equally important is recognizing when two-pointer is the wrong approach. Here are red flags:

Red Flags Against Two-Pointer

•Optimal Substructure + Overlapping Subproblems — These signal dynamic programming, not two-pointer. E.g., "minimum cost path" or "count ways to reach target".
•Unsorted data with no clear ordering strategy — If you can't define a meaningful pointer movement direction, two-pointer won't help.
•Need to consider all subsets/combinations — Two-pointer processes elements linearly. If you need exponential exploration, use backtracking.
•Non-linear structures — Trees, graphs, matrices with arbitrary traversal patterns require different techniques.
•Backtracking required — If you might need to revisit a discarded element based on later information, two-pointer's one-way nature doesn't fit.
•Global optimization without greedy property — Two-pointer makes locally optimal moves. If the problem lacks a greedy structure, it may fail.

Example: Longest Increasing Subsequence (LIS)

Can we solve LIS with two-pointer? Let's analyze:

Input is an array ✓
We're looking for a subsequence (not contiguous) ✗
Elements don't need to be adjacent ✗
The problem has optimal substructure (LIS is built from smaller LIS)

Two-pointer fails because:

Moving pointers doesn't tell us about the best subsequence
We need to consider elements in the middle, not just ends
The problem has overlapping subproblems → dynamic programming is correct

Example: Subarray with Given Sum (Unsorted)

For positive-only arrays, sliding window (a form of two-pointer) works. For arrays with negatives... it doesn't! Why?

Adding an element might increase OR decrease the sum
No monotonicity → can't decide pointer direction
Use prefix sums + hash map instead

red_flag_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# RED FLAG: Longest Increasing Subsequence
# Two-pointer CANNOT solve this efficiently
 
# Wrong approach: trying two-pointer
def lis_two_pointer_wrong(nums):
    # This doesn't work! Two-pointer can't find optimal subsequence
    # because LIS elements may not be at the ends
    pass
 
# Correct approach: Dynamic Programming O(n^2) or O(n log n)
def lis_correct(nums: list[int]) -> int:
    if not nums:
        return 0
    
    dp = [1] * len(nums)  # dp[i] = LIS ending at index i
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)
 
 
# RED FLAG: Subarray sum with negatives
# Two-pointer/sliding window fails due to lack of monotonicity
 
# For positive-only: sliding window works
def subarray_sum_positive(nums: list[int], target: int) -> list[int]:
    """Works for positive-only arrays."""
    left = 0
    current_sum = 0
    
    for right in range(len(nums)):
        current_sum += nums[right]
        
        while current_sum > target and left <= right:
            current_sum -= nums[left]
            left += 1
        
        if current_sum == target:
            return [left, right]
    
    return []
 
# For arrays with negatives: need different approach
def subarray_sum_any(nums: list[int], target: int) -> list[int]:
    """Works for any array using prefix sums."""
    prefix_sum = 0
    seen = {0: -1}  # prefix_sum -> index
    
    for i, num in enumerate(nums):
        prefix_sum += num
        
        if prefix_sum - target in seen:
            return [seen[prefix_sum - target] + 1, i]
        
        seen[prefix_sum] = i
    
    return []
 
 
# Example where two-pointer fails:
# nums = [1, -2, 3, -1, 2], target = 3
# Subarray [3] or [1, -2, 3, -1, 2] both sum to 3 or 3
# But sliding window would fail because adding -2 decreases sum
# then adding 3 increases it - no monotonicity!

The Monotonicity Test

Borderline Cases: When Two-Pointer Might Work

Some problems aren't obviously two-pointer, but can be transformed into two-pointer problems with the right insight:

Borderline Scenarios

•Unsorted array → Sort first — If the problem allows O(n log n) time and order doesn't need to be preserved, sort and apply converging pointers.
•Subarray problems with positive numbers — These become sliding window problems, which are a form of same-direction two-pointer.
•Problems requiring index tracking — Map elements to indices, sort by value, then use two-pointer on the value order.
•Two arrays problems — One pointer per array, advancing based on comparisons.
•Circular array — Can sometimes be linearized by doubling the array or handling wraparound.

Case Study: Two Sum (Unsorted)

The classic Two Sum problem with an unsorted array:

Option 1: Sort + Two-Pointer

Sort the array (but lose original indices)
Store (value, original_index) pairs, sort by value
Use converging two-pointer
Time: O(n log n), Space: O(n)

Option 2: Hash Map

Store seen values and their indices
For each element, check if (target - element) is in the map
Time: O(n), Space: O(n)

For unsorted Two Sum, the hash map approach is often better (linear time). But if you need k-sum or the data is already sorted, two-pointer shines.

borderline_examples.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# BORDERLINE: Two Sum on unsorted array
# Can be solved with two-pointer after sorting
 
def two_sum_with_indices(nums: list[int], target: int) -> list[int]:
    """
    Two Sum returning original indices, using sort + two-pointer.
    
    Time: O(n log n)
    Space: O(n) for storing index pairs
    """
    # Store (value, original_index) pairs
    indexed = [(val, idx) for idx, val in enumerate(nums)]
    indexed.sort(key=lambda x: x[0])  # Sort by value
    
    left, right = 0, len(indexed) - 1
    
    while left < right:
        current_sum = indexed[left][0] + indexed[right][0]
        
        if current_sum == target:
            return [indexed[left][1], indexed[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []
 
 
# BORDERLINE: Subarray with maximum sum of length k
# This is sliding window (same-direction two-pointer)
 
def max_sum_subarray_k(nums: list[int], k: int) -> int:
    """
    Find max sum of subarray of length exactly k.
    
    Sliding window: maintain window of size k.
    Time: O(n)
    Space: O(1)
    """
    if len(nums) < k:
        return 0
    
    # Initialize with first window
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    # Slide window
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # Add new, remove old
        max_sum = max(max_sum, window_sum)
    
    return max_sum
 
 
# BORDERLINE: Two arrays, find pair closest to target
def two_array_closest_pair(arr1: list[int], arr2: list[int], target: int) -> tuple:
    """
    Find one element from each array such that their sum is closest to target.
    
    Approach: Sort both, use converging-like logic.
    """
    arr1.sort()
    arr2.sort()
    
    i = 0
    j = len(arr2) - 1
    closest = float('inf')
    best_pair = (arr1[0], arr2[0])
    
    while i < len(arr1) and j >= 0:
        current_sum = arr1[i] + arr2[j]
        
        if abs(current_sum - target) < abs(closest - target):
            closest = current_sum
            best_pair = (arr1[i], arr2[j])
        
        if current_sum < target:
            i += 1
        elif current_sum > target:
            j -= 1
        else:
            return best_pair  # Exact match
    
    return best_pair
 
 
# Test
print(two_sum_with_indices([3, 2, 4], 6))  # [1, 2] (2 + 4 = 6)
print(max_sum_subarray_k([1, 4, 2, 10, 2, 3, 1, 0, 20], 4))  # 24 (10+2+3+1=16? Let's see... 2+3+1+0=6, 3+1+0+20=24)
print(two_array_closest_pair([1, 4, 5, 7], [10, 20, 30, 40], 32))  # (7, 30) sum=37 or (4, 30) sum=34

Alternative Techniques When Two-Pointer Fails

When two-pointer doesn't apply, here are the common alternatives and when to use each:

Alternative Techniques and When to Use Them
Technique	When to Use	Example Problems
Hash Map/Set	Need O(1) lookups, unsorted data, counting	Two Sum, subarray sum with negatives
Dynamic Programming	Optimal substructure + overlapping subproblems	LIS, edit distance, coin change
Binary Search	Sorted data, looking for specific element	Search in rotated array, peak finding
Sliding Window	Contiguous subarray/substring optimization	Max sum subarray of size k
Stack	Matching pairs, next greater element, parentheses	Valid parentheses, daily temperatures
Prefix Sum	Range sum queries, subarray sums	Subarray sum equals k
Divide and Conquer	Problem splits into independent subproblems	Merge sort, closest pair of points
Backtracking	Need to explore all possibilities	Permutations, combinations, N-queens

Decision Flowchart:

Is the data sorted or can you sort it?
├─ YES → Is it a pair/triple finding problem?
│         ├─ YES → Use CONVERGING TWO-POINTER
│         └─ NO → Is it searching for a specific value?
│                  ├─ YES → Use BINARY SEARCH
│                  └─ NO → Consider SLIDING WINDOW or other
│
└─ NO → Need O(1) lookups or counting?
         ├─ YES → Use HASH MAP/SET
         └─ NO → Does problem have optimal substructure?
                  ├─ YES → Use DYNAMIC PROGRAMMING
                  └─ NO → Need to explore all possibilities?
                           ├─ YES → Use BACKTRACKING
                           └─ NO → Analyze further...

Multiple Techniques Combined

The Two-Pointer Decision Checklist

When you encounter a new problem, run through this checklist:

Step-by-Step Evaluation

•Is it an array/string/linked list problem? If not (tree, graph, etc.), two-pointer likely doesn't apply directly.
•Is the data sorted or can you sort it without losing information? If yes, converging two-pointer becomes viable.
•Is there a monotonic relationship? Moving a pointer should predictably increase/decrease some target metric.
•Are you looking for pairs, checking symmetry, or doing in-place modification? These are classic two-pointer scenarios.
•Can you make progress without backtracking? Two-pointer moves forward only. If you might need to reconsider earlier elements based on later ones, consider DP or backtracking.
•Is O(n) time and O(1) space achievable and required? Two-pointer often provides this. If O(n) time with O(n) space is acceptable, hash maps might be simpler.

Quick Heuristics:

If you see...	Think...
"Sorted array"	Converging two-pointer
"In-place"	Same-direction reader/writer
"Find pair/triple"	Two-pointer or hash map
"Palindrome"	Converging from both ends
"O(1) space"	Two-pointer or careful in-place
"Cycle in list"	Fast-slow pointers
"Merge sorted"	One pointer per array
"Partition/segregate"	Same-direction swap pointer

Practice Problems Categorized

To solidify pattern recognition, here are problems categorized by technique:

Converging Two-Pointer Problems
Problem	Difficulty	Key Insight
Two Sum II (sorted)	Easy	Classic converging sum search
3Sum	Medium	Fix one + two-pointer for pairs
Container With Most Water	Medium	Move shorter wall inward
Valid Palindrome	Easy	Compare from both ends
Trapping Rain Water	Hard	Two-pointer with max tracking
4Sum	Medium	Two loops + two-pointer

Same-Direction Two-Pointer Problems
Problem	Difficulty	Key Insight
Remove Duplicates from Sorted Array	Easy	Reader-writer paradigm
Remove Element	Easy	Skip unwanted values
Move Zeroes	Easy	Swap non-zeros forward
Sort Colors	Medium	Dutch National Flag, 3 pointers
Partition List (linked list)	Medium	Two separate lists merged

Fast-Slow Pointer Problems
Problem	Difficulty	Key Insight
Linked List Cycle	Easy	Floyd's cycle detection
Linked List Cycle II (find start)	Medium	Two-phase: detect + find start
Find the Duplicate Number	Medium	Array as linked list
Middle of the Linked List	Easy	Fast reaches end, slow is middle
Happy Number	Easy	Sequence forms cycle or terminates

NOT Two-Pointer (Common Confusions)
Problem	Correct Approach	Why Not Two-Pointer
Longest Increasing Subsequence	DP or binary search	Non-contiguous, needs optimal substructure
Subarray Sum (with negatives)	Hash map + prefix sum	No monotonicity
Minimum Window Substring	Sliding window + hash map	Need tracking structure, not pure two-pointer
Edit Distance	Dynamic programming	2D optimization problem

Summary: Pattern Recognition Mastery

You now have a comprehensive framework for recognizing when two-pointer applies. Let's consolidate:

Key Decision Points

•Monotonicity is key — If pointer movement doesn't have a predictable effect on your target metric, two-pointer won't work.
•Keywords trigger patterns — 'Sorted array', 'in-place', 'O(1) space', 'palindrome', 'cycle' all suggest two-pointer variants.
•Red flags mean pivot — Optimal substructure, backtracking need, no monotonicity → consider DP, hash maps, or other techniques.
•Transformation enables technique — Unsorted data can sometimes be sorted. Index tracking can add the information you need.
•Combined techniques are common — Many problems use loop + two-pointer, binary search + two-pointer, or hash map + two-pointer.

The Master Heuristic:

Two-pointer works when you can guarantee that each pointer movement eliminates many candidates from consideration, and you never need to revisit eliminated candidates.

If both conditions hold, two-pointer likely applies. If either fails, look elsewhere.

Module Complete

5 / 5