Why Two Pointer Technique Beats Brute Force in DSA Rust - Why This Pattern

Mental Model

Two pointers move through data in a smart way to avoid checking everything twice.

Analogy: Imagine two friends walking from opposite ends of a hallway to find a meeting point instead of one friend walking back and forth repeatedly.

Array: [1] -> [2] -> [3] -> [4] -> [5] -> null
Pointers: ↑left                             ↑right

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5], find pairs that sum to 6

Goal: Find pairs adding to 6 without checking every pair twice

Step 1: Set left pointer at index 0 (value 1), right pointer at index 4 (value 5)

[1]↑left -> [2] -> [3] -> [4] -> [5]↑right -> null

Why: Start from both ends to check sums efficiently

Step 2: Sum values at left and right: 1 + 5 = 6, pair found

[1]↑left -> [2] -> [3] -> [4] -> [5]↑right -> null

Why: Found a valid pair, now move pointers to find others

Step 3: Move left pointer right to index 1 (value 2), right pointer left to index 3 (value 4)

[1] -> [2]↑left -> [3] -> [4]↑right -> [5] -> null

Why: Check next possible pair without repeating previous pairs

Step 4: Sum values at left and right: 2 + 4 = 6, pair found

[1] -> [2]↑left -> [3] -> [4]↑right -> [5] -> null

Why: Found another valid pair

Step 5: Move left pointer right to index 2 (value 3), right pointer left to index 2 (value 3)

[1] -> [2] -> [3]↑left↑right -> [4] -> [5] -> null

Why: Pointers meet, no more pairs to check

Result:

[1] -> [2] -> [3] -> [4] -> [5] -> null
Pairs found: (1,5), (2,4)

Annotated Code

DSA Rust

struct Solution;

impl Solution {
    pub fn two_pointer_pairs(arr: &[i32], target: i32) -> Vec<(i32, i32)> {
        let mut left = 0;
        let mut right = arr.len().saturating_sub(1);
        let mut result = Vec::new();

        while left < right {
            let sum = arr[left] + arr[right];
            if sum == target {
                result.push((arr[left], arr[right]));
                left += 1; // move left pointer right
                right -= 1; // move right pointer left
            } else if sum < target {
                left += 1; // increase sum by moving left pointer right
            } else {
                right -= 1; // decrease sum by moving right pointer left
            }
        }
        result
    }
}

fn main() {
    let arr = [1, 2, 3, 4, 5];
    let target = 6;
    let pairs = Solution::two_pointer_pairs(&arr, target);
    for (a, b) in pairs {
        println!("({}, {})", a, b);
    }
}

while left < right {

continue until pointers meet to avoid repeated checks

let sum = arr[left] + arr[right];

calculate sum of values at pointers

if sum == target {

found a pair matching target sum

left += 1; // move left pointer right

advance left pointer to find new pairs

right -= 1; // move right pointer left

move right pointer inward to avoid duplicates

} else if sum < target {

sum too small, move left pointer right to increase sum

} else {

sum too large, move right pointer left to decrease sum

Output

(1, 5)

(2, 4)

Complexity Analysis

Time: O(n) because each pointer moves at most n steps through the array once

Space: O(k) where k is number of pairs found, for storing results

vs Alternative: Brute force checks all pairs in O(n^2), two pointer reduces to O(n) by smart pointer moves

Edge Cases

empty array

returns empty pairs list immediately

DSA Rust

let mut right = arr.len().saturating_sub(1);

array with one element

no pairs found because left < right condition fails

DSA Rust

while left < right {

no pairs sum to target

returns empty pairs list after checking all possibilities

DSA Rust

while left < right {

When to Use This Pattern

When you need to find pairs or subarrays with certain properties in sorted data, use two pointers to reduce time from quadratic to linear.

Common Mistakes

Mistake: Moving only one pointer regardless of sum comparison
Fix: Move left pointer right if sum is too small, right pointer left if sum is too large

Mistake: Not stopping when pointers meet or cross
Fix: Use while left < right condition to avoid invalid pairs

Summary

It finds pairs in sorted data efficiently by moving two pointers inward.

Use it when you want to find pairs or ranges with a target sum or condition in sorted arrays.

The key insight is that moving pointers based on sum comparison avoids checking all pairs.

Practice

1. What is the main advantage of the two pointer technique over brute force in array problems?

easy

A. It always finds the maximum element in the array

B. It reduces time complexity by avoiding nested loops

C. It requires sorting the array first in all cases

D. It uses more memory to store intermediate results

Solution

1. Step 1: Understand brute force approach

   Brute force often uses nested loops, leading to higher time complexity like O(n²).

2. Step 2: Compare with two pointer technique

   Two pointer technique uses two indices moving through the array, reducing complexity to O(n).

3. Final Answer:

   It reduces time complexity by avoiding nested loops -> Option B

4. Quick Check:

   Two pointer = faster than brute force [OK]

Hint: Two pointers move linearly, avoiding double loops [OK]

Common Mistakes:

• Thinking two pointer always needs sorting
• Confusing memory use with speed
• Assuming it finds max element always

2. Which of the following is the correct Rust syntax to initialize two pointers at the start and end of a vector named nums?

easy

A. let (mut left, mut right) = (0, nums.len() - 1);

B. let left = 0; let right = nums.len();

C. let (left, right) = (nums[0], nums[nums.len()]);

D. let mut left = nums.len() - 1; let mut right = 0;

Solution

1. Step 1: Identify pointer initialization

   Two pointers are indices, so left starts at 0 and right at last index (length - 1).

2. Step 2: Check Rust syntax correctness

   let (mut left, mut right) = (0, nums.len() - 1); correctly declares mutable variables with proper tuple assignment and index calculation.

3. Final Answer:

   let (mut left, mut right) = (0, nums.len() - 1); -> Option A

4. Quick Check:

   Correct Rust pointer init = let (mut left, mut right) = (0, nums.len() - 1); [OK]

Hint: Pointers are indices: start=0, end=length-1 [OK]

Common Mistakes:

• Using nums.len() instead of nums.len() - 1 for last index
• Assigning values from vector elements instead of indices
• Not declaring pointers as mutable when needed

3. What will be the output of the following Rust code snippet?

let nums = vec![1, 2, 3, 4, 5];
let mut left = 0;
let mut right = nums.len() - 1;
let mut sum_pairs = Vec::new();
while left < right {
    sum_pairs.push(nums[left] + nums[right]);
    left += 1;
    right -= 1;
}
println!("{:?}", sum_pairs);

medium

A. [5, 6, 7]

B. [6, 7]

C. [5, 7]

D. [6, 6]

Solution

1. Step 1: Trace pointer movements and sums

   Initially left=0, right=4; sums: nums[0]+nums[4]=1+5=6; then left=1, right=3; sums: 2+4=6; loop stops when left=2, right=2.

2. Step 2: Collect sums in vector

   sum_pairs contains [6, 6] after loop ends.

3. Final Answer:

   [6, 6] -> Option D

4. Quick Check:

   Pairs sum = [6, 6] [OK]

Hint: Sum pairs from ends moving inward [OK]

Common Mistakes:

• Including middle element sum when left == right
• Miscalculating indices or sums
• Assuming loop runs when left == right

4. Identify the bug in this Rust code using two pointers to find if a pair sums to 10:

let nums = vec![1, 3, 5, 7, 9];
let mut left = 0;
let mut right = nums.len();
while left < right {
    let sum = nums[left] + nums[right];
    if sum == 10 {
        println!("Found");
        break;
    } else if sum < 10 {
        left += 1;
    } else {
        right -= 1;
    }
}

medium

A. right is initialized to nums.len(), which is out of bounds

B. left pointer should start at nums.len() - 1

C. The loop condition should be left <= right

D. The sum calculation should use nums[left] - nums[right]

Solution

1. Step 1: Check pointer initialization

   right is set to nums.len(), which is one past the last valid index (out of bounds).

2. Step 2: Correct pointer initialization

   right should be nums.len() - 1 to point to last element.

3. Final Answer:

   right is initialized to nums.len(), which is out of bounds -> Option A

4. Quick Check:

   Index out of bounds error = right is initialized to nums.len(), which is out of bounds [OK]

Hint: Last index = length - 1, not length [OK]

Common Mistakes:

• Using length as index causing runtime panic
• Changing loop condition incorrectly
• Misusing sum calculation operator

5. Given a sorted vector nums, how can the two pointer technique be used to find all unique pairs that sum to a target value without duplicates?

hard

A. Sort the vector first, then use a hash map to find complements

B. Use nested loops to check all pairs and store unique pairs in a set

C. Use two pointers from start and end, move inward skipping duplicates after finding a pair

D. Use a single pointer and binary search for complement for each element

Solution

1. Step 1: Initialize two pointers at start and end

   Set left = 0 and right = nums.len() - 1 to scan pairs from both ends.

2. Step 2: Move pointers inward and skip duplicates

   When a pair sums to target, record it, then move pointers skipping over duplicate values to avoid repeated pairs.

3. Final Answer:

   Use two pointers from start and end, move inward skipping duplicates after finding a pair -> Option C

4. Quick Check:

   Two pointer + skip duplicates = unique pairs [OK]

Hint: Skip duplicates after finding pairs to avoid repeats [OK]

Common Mistakes:

• Using nested loops causing slow performance
• Not skipping duplicates leading to repeated pairs
• Using hash map or binary search unnecessarily