Two Pointer Technique on Arrays in DSA Rust

Mental Model

Use two markers moving through the array to find or compare elements efficiently without extra space.

Analogy: Imagine two friends starting at opposite ends of a hallway, walking towards each other to find a meeting point or check something together.

Array: [1, 3, 5, 7, 9]
Pointers: ↑left               right↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9], find if two numbers sum to 10

Goal: Check if any two numbers in the array add up to 10 using two pointers

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

[1↑, 3, 5, 7, 9↑]

Why: Start checking pairs from both ends to cover all possibilities efficiently

Step 2: Sum values at left and right: 1 + 9 = 10, found target sum

[1↑, 3, 5, 7, 9↑]

Why: Sum matches target, so we can stop searching

Result:

[1↑, 3, 5, 7, 9↑] -> Found pair (1, 9) that sums to 10

Annotated Code

DSA Rust

fn two_pointer_sum(arr: &[i32], target: i32) -> bool {
    let mut left = 0;
    let mut right = arr.len().saturating_sub(1);
    while left < right {
        let sum = arr[left] + arr[right];
        if sum == target {
            return true; // found the pair
        } else if sum < target {
            left += 1; // increase sum by moving left pointer right
        } else {
            right -= 1; // decrease sum by moving right pointer left
        }
    }
    false // no pair found
}

fn main() {
    let arr = [1, 3, 5, 7, 9];
    let target = 10;
    let result = two_pointer_sum(&arr, target);
    println!("{}", result);
}

let mut left = 0;

initialize left pointer at start of array

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

initialize right pointer at end of array

while left < right {

loop until pointers meet or cross

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

calculate sum of values at pointers

if sum == target { return true; }

if sum matches target, return success

else if sum < target { left += 1; }

if sum too small, move left pointer right to increase sum

else { right -= 1; }

if sum too large, move right pointer left to decrease sum

Output

true

Complexity Analysis

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

Space: O(1) because no extra space is used besides pointers

vs Alternative: Compared to nested loops O(n^2), two pointers reduce time by scanning array only once

Edge Cases

empty array

returns false immediately because no pairs exist

DSA Rust

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

array with one element

returns false because left pointer is not less than right pointer

DSA Rust

while left < right {

no pair sums to target

returns false after pointers cross without finding pair

DSA Rust

return false // no pair found

When to Use This Pattern

When you need to find pairs or compare elements from both ends of a sorted array, use two pointers to reduce time from quadratic to linear.

Common Mistakes

Mistake: Not moving pointers correctly when sum is less or greater than target
Fix: Move left pointer right if sum is less than target, move right pointer left if sum is greater

Summary

It finds pairs in a sorted array efficiently using two pointers moving inward.

Use it when searching pairs or conditions involving two elements in sorted arrays.

The key is adjusting pointers based on comparison to target to avoid checking all pairs.

Practice

1. What is the main idea behind the Two Pointer Technique when used on arrays?

easy

A. Use recursion to divide the array into two parts

B. Use two arrays to store intermediate results

C. Sort the array twice before processing

D. Use two indices to scan the array from different ends or positions simultaneously

Solution

1. Step 1: Understand the technique

   The two pointer technique uses two indices or pointers to traverse the array, often from opposite ends or different positions.

2. Step 2: Identify the purpose

   This helps solve problems like finding pairs, removing duplicates, or partitioning efficiently without extra space.

3. Final Answer:

   Use two indices to scan the array from different ends or positions simultaneously -> Option D

4. Quick Check:

   Two pointers = two indices scanning array [OK]

Hint: Think of two fingers moving on array from different sides [OK]

Common Mistakes:

• Confusing two pointers with two separate arrays
• Assuming sorting is always required
• Thinking recursion is part of two pointer technique

2. Which of the following Rust code snippets correctly initializes two pointers for the two pointer technique on a vector arr?

easy

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

B. let (mut left, mut right) = (0, arr.len() - 1);

C. let (mut left, mut right) = (1, arr.len());

D. let (left, right) = (arr.len(), 0);

Solution

1. Step 1: Check pointer initialization

   Two pointers usually start at the beginning (0) and end (length - 1) of the array.

2. Step 2: Verify mutability and valid indices

   Pointers must be mutable to move, and indices must be within array bounds (0 to len-1).

3. Final Answer:

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

4. Quick Check:

   Start pointers at 0 and len-1 with mut [OK]

Hint: Start pointers at 0 and last index, make them mutable [OK]

Common Mistakes:

• Using non-mutable pointers when they need to move
• Setting pointers outside array bounds
• Swapping start and end indices

3. What will be the output of the following Rust code using two pointers?

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

medium

A. [6, 6]

B. [6, 7]

C. [6, 5]

D. [5, 7]

Solution

1. Step 1: Trace pointer movements and sums

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

2. Step 2: Collect sums in vector

   The sums collected are [6, 6].

3. Final Answer:

   [6, 6] -> Option A

4. Quick Check:

   Pairs sums = [6, 6] [OK]

Hint: Add elements at left and right, move pointers inward [OK]

Common Mistakes:

• Not stopping loop when pointers meet
• Adding wrong pairs or indices
• Off-by-one errors in pointer updates

4. Identify the bug in this Rust code snippet using two pointers to find if a sorted array contains two numbers that sum to 10:

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

medium

A. The loop condition should be left <= right

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

C. right is initialized to arr.len(), which is out of bounds

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

Solution

1. Step 1: Check pointer initialization

   right is set to arr.len(), which is one past the last valid index (arr.len() - 1).

2. Step 2: Understand consequences

   Accessing arr[right] causes an out-of-bounds error and program panic.

3. Final Answer:

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

4. Quick Check:

   Array indices go 0 to len-1 [OK]

Hint: Check if pointers are within valid index range [OK]

Common Mistakes:

• Using arr.len() as index instead of arr.len() - 1
• Incorrect loop condition allowing invalid access
• Mixing addition and subtraction in sum calculation

5. Given a sorted array of integers, write a Rust function using the two pointer technique to return all unique pairs that sum to a target value. Which approach correctly avoids duplicate pairs?

hard

A. Move left and right pointers inward, skipping duplicates after finding a valid pair

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

C. Sort the array again inside the loop to remove duplicates

D. Only move the left pointer forward regardless of sum comparison

Solution

1. Step 1: Use two pointers from start and end

   Initialize left at 0 and right at last index, move inward based on sum comparison.

2. Step 2: Skip duplicates after finding a valid pair

   After adding a pair, increment left while next value equals current, decrement right similarly to avoid duplicates.

3. Final Answer:

   Move left and right pointers inward, skipping duplicates after finding a valid pair -> Option A

4. Quick Check:

   Skip duplicates by moving pointers after valid pair [OK]

Hint: After finding pair, skip duplicates by moving pointers [OK]

Common Mistakes:

• Not skipping duplicates causing repeated pairs
• Using nested loops instead of two pointers
• Moving only one pointer regardless of sum