Two Pointer Technique on Arrays in DSA Rust - Execution Trace

Concept Flow - Two Pointer Technique on Arrays

Initialize two pointers: left=0, right=end

↓

Check condition: left < right?

No→Stop

Yes↓

Compare or process elements at left and right

↓

Move left pointer

↓

Repeat check condition

Start with two pointers at array ends, move them based on conditions until they meet or cross.

Execution Sample

DSA Rust

let arr = [1, 3, 5, 7, 9];
let mut left = 0;
let mut right = arr.len() - 1;
while left < right {
    if arr[left] + arr[right] == 10 {
        break;
    } else if arr[left] + arr[right] < 10 {
        left += 1;
    } else {
        right -= 1;
    }
}

Find two numbers in a sorted array that sum to 10 using two pointers.

Execution Table

Step	Operation	left	right	arr[left]	arr[right]	Sum	Action	Visual State
1	Initialize pointers	0	4	1	9	10	Check sum == 10	[1, 3, 5, 7, 9]
2	Sum equals 10	0	4	1	9	10	Break loop	[1, 3, 5, 7, 9]
3	End	0	4	1	9	10	Pointers stopped	[1, 3, 5, 7, 9]

💡 Sum at left=0 and right=4 is 10, condition met, loop stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
left	0	0	0	0
right	4	4	4	4
sum	N/A	10	10	10

Key Moments - 3 Insights

Why do we stop when left pointer is not less than right pointer?

Because when left >= right, pointers have met or crossed, meaning all pairs have been checked (see execution_table step 1 condition).

Why do we move left pointer when sum is less than target?

Because increasing left moves to a larger number in sorted array, increasing sum.

Why do we move right pointer when sum is greater than target?

Because decreasing right moves to a smaller number, reducing sum to approach target.

Visual Quiz - 3 Questions

Look at the execution_table at step 1, what is the sum of arr[left] + arr[right]?

A 10

B 9

C 8

D 11

💡 Hint

Check the 'Sum' column in execution_table row with Step 1.

At which step does the loop stop because the sum equals the target?

A Step 1

B Step 2

C Step 3

D It never stops

💡 Hint

Look at the 'Action' column where it says 'Break loop'.

If the target sum was 12 instead of 10, which pointer would move first?

A left pointer

B right pointer

C both pointers simultaneously

D no pointer moves

💡 Hint

Refer to key_moments about moving pointers when sum is less than target.

Concept Snapshot

Two Pointer Technique on Arrays:
- Use two pointers at start and end.
- Move pointers based on condition (e.g., sum comparison).
- Stop when pointers meet or condition met.
- Efficient for sorted arrays.
- Commonly used for pair sum problems.

Full Transcript

The two pointer technique uses two indexes starting at opposite ends of an array. We check the sum of elements at these pointers. If the sum matches the target, we stop. If the sum is less, we move the left pointer right to increase sum. If the sum is more, we move the right pointer left to decrease sum. This continues until pointers meet or condition is met. This method is efficient for sorted arrays to find pairs with a given sum.

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