Two Pointer Technique on Arrays in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Pointer Sum Check

What is the output of this Rust code that uses two pointers to check if any two numbers sum to 9?

DSA Rust

fn main() {
    let arr = [1, 2, 4, 4, 5, 6];
    let target = 9;
    let mut left = 0;
    let mut right = arr.len() - 1;
    let mut found = false;

    while left < right {
        let sum = arr[left] + arr[right];
        if sum == target {
            found = true;
            break;
        } else if sum < target {
            left += 1;
        } else {
            right -= 1;
        }
    }

    println!("{}", found);
}

A false

B Compilation error

C Runtime panic

D true

💡 Hint

Think about pairs that add up to 9 in the sorted array.

The code uses two pointers starting at the beginning and end of the sorted array. It checks sums and moves pointers accordingly. The pair (4,5) sums to 9, so found becomes true and prints true.

❓ Predict Output

intermediate

Result of Removing Duplicates Using Two Pointers

What will be printed after running this Rust code that removes duplicates from a sorted array using two pointers?

DSA Rust

fn main() {
    let mut arr = vec![1, 1, 2, 2, 3, 4, 4, 5];
    let mut i = 0;
    for j in 1..arr.len() {
        if arr[j] != arr[i] {
            i += 1;
            arr[i] = arr[j];
        }
    }
    arr.truncate(i + 1);
    println!("{:?}", arr);
}

A [1, 1, 2, 3, 4, 5]

B [1, 2, 3, 4, 5]

C [1, 2, 2, 3, 4, 5]

D [1, 2, 3, 4, 4, 5]

💡 Hint

The code keeps unique elements at the front and truncates the vector.

The two pointers i and j move through the vector. When a new unique element is found, it is placed at i+1. Finally, the vector is truncated to keep only unique elements.

🔧 Debug

advanced

Identify the Error in Two Pointer Partitioning

This Rust code tries to partition an array so that all even numbers come before odd numbers using two pointers. What error will it cause when run?

DSA Rust

fn main() {
    let mut arr = vec![2, 8, 4, 12, 10, 6];
    let mut left = 0;
    let mut right = arr.len() - 1;

    while left < right {
        while left < right && arr[left] % 2 == 0 {
            left += 1;
        }
        while left < right && arr[right] % 2 == 1 {
            right -= 1;
        }
        if left < right {
            arr.swap(left, right);
            left += 1;
            right -= 1;
        }
    }
    println!("{:?}", arr);
}

A Runtime panic due to index out of bounds

B Infinite loop

C Correct partitioned array output

D Compilation error

💡 Hint

Check the inner while loops for pointer increments without boundary checks.

The inner while loops increment left and decrement right without checking if they go out of array bounds. This can cause left or right to exceed valid indices, leading to a runtime panic.

🚀 Application

advanced

Find the Maximum Water Container Area

Given an array representing heights of vertical lines, which option correctly computes the maximum area of water the container can hold using two pointers?

DSA Rust

fn max_area(height: Vec<i32>) -> i32 {
    let mut left = 0;
    let mut right = height.len() - 1;
    let mut max_area = 0;

    while left < right {
        let width = (right - left) as i32;
        let min_height = if height[left] < height[right] { height[left] } else { height[right] };
        let area = width * min_height;
        if area > max_area {
            max_area = area;
        }
        if height[left] < height[right] {
            left += 1;
        } else {
            right -= 1;
        }
    }
    max_area
}

fn main() {
    let heights = vec![1,8,6,2,5,4,8,3,7];
    println!("{}", max_area(heights));
}

A 36

B 48

C 49

D 56

💡 Hint

The maximum area is found between lines at indices 1 and 8.

The two pointer approach calculates area between left and right pointers, moving the pointer with smaller height inward. The maximum area for the given input is 49.

🧠 Conceptual

expert

Two Pointer Technique for Palindrome Check

Which statement correctly describes why the two pointer technique is efficient for checking if a string is a palindrome?

A It compares characters from both ends moving towards the center, stopping early if mismatch found, avoiding full traversal.

B It reverses the string and compares it to the original, which is faster than character by character comparison.

C It sorts the characters and checks if the sorted string equals the original, ensuring palindrome property.

D It uses a stack to store half the characters and compares with the other half, reducing space complexity.

💡 Hint

Think about how two pointers move and when the check stops.

The two pointer technique starts from both ends and moves inward, comparing characters. It stops immediately if a mismatch is found, making it efficient by avoiding unnecessary checks.

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