Two Pointer Technique on Arrays in DSA C#

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 quickly.

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

Dry Run Walkthrough

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

Goal: Find two elements whose sum is 12 using two pointers

Step 1: Initialize left pointer at index 0 and right pointer at index 4

1 [left->1] -> 3 -> 5 -> 7 -> 9 [right->9]

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

Step 2: Calculate sum: 1 + 9 = 10, which is less than 12, move left pointer right

1 -> 3 [left->3] -> 5 -> 7 -> 9 [right->9]

Why: Sum too small, increase it by moving left pointer to a bigger number

Step 3: Calculate sum: 3 + 9 = 12, found the target sum

1 -> 3 [left->3] -> 5 -> 7 -> 9 [right->9]

Why: Sum matches target, we found the pair

Result:

1 -> 3 [left->3] -> 5 -> 7 -> 9 [right->9]
Answer: Pair found (3, 9)

Annotated Code

DSA C#

using System;

class TwoPointerArray {
    public static void FindPairWithSum(int[] arr, int target) {
        int left = 0;
        int right = arr.Length - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == target) {
                Console.WriteLine($"Pair found ({arr[left]}, {arr[right]})");
                return;
            } else if (sum > target) {
                right--; // decrease sum by moving right pointer left
            } else {
                left++; // increase sum by moving left pointer right
            }
        }
        Console.WriteLine("No pair found");
    }

    static void Main() {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 12;
        FindPairWithSum(arr, target);
    }
}

int left = 0; int right = arr.Length - 1;

Initialize two pointers at start and end of array

while (left < right) {

Loop until pointers cross to check all pairs

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

Calculate sum of elements at pointers

if (sum == target) {

Check if sum matches target

right--;

Decrease right pointer to decrease sum when sum is too large

left++;

Increase left pointer to increase sum when sum is too small

Output

Pair found (3, 9)

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²), this method is much faster by using two pointers to scan from both ends

Edge Cases

Empty array

No pair found, function exits quickly

DSA C#

while (left < right) {

Array with one element

No pair found because left is not less than right

DSA C#

while (left < right) {

No two elements sum to target

Loop ends without finding pair, prints 'No pair found'

DSA C#

Console.WriteLine("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 when sum is less, move right pointer left when sum is greater

Mistake: Using two nested loops instead of two pointers
Fix: Use two pointers to scan from both ends for better efficiency

Summary

Find pairs or compare elements efficiently by using two pointers moving from opposite ends.

Use when working with sorted arrays to find pairs or conditions involving two elements.

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

Practice

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

easy

A. Use two indices to traverse the array from different ends or positions simultaneously

B. Use one pointer to traverse and another to store values

C. Sort the array first and then use binary search

D. Use recursion to split the array into two parts

Solution

1. Step 1: Understand the two pointer approach

   The technique uses two pointers (indices) to scan the array from different positions, often from start and end. This helps solve problems efficiently by reducing the number of iterations compared to nested loops.

2. Final Answer:

   Use two indices to traverse the array from different ends or positions simultaneously -> Option A

3. Quick Check:

   Two pointers move from different ends = D [OK]

Hint: Two pointers move from start and end to meet in middle [OK]

Common Mistakes:

• Thinking it always requires sorting first
• Using only one pointer instead of two
• Confusing with recursion or binary search

2. Which of the following is the correct syntax to initialize two pointers left and right for an array arr in C#?

easy

A. int left = -1, right = arr.Length + 1;

B. int left = 1, right = arr.Length;

C. int left = arr.Length, right = 0;

D. int left = 0, right = arr.Length - 1;

Solution

1. Step 1: Understand array indexing and initialize pointers correctly

   Arrays start at index 0 and end at index Length - 1. Left pointer starts at 0 (first element), right pointer at Length - 1 (last element).

2. Final Answer:

   int left = 0, right = arr.Length - 1; -> Option D

3. Quick Check:

   Start at 0 and end at Length-1 = A [OK]

Hint: Start left at 0, right at length minus one [OK]

Common Mistakes:

• Starting right pointer at arr.Length (out of bounds)
• Starting left pointer at 1 instead of 0
• Using negative indices

3. What will be the output of the following C# code?

int[] arr = {1, 2, 3, 4, 5, 6};
int left = 0, right = arr.Length - 1;
int sum = 0;
while (left < right) {
    sum += arr[left] + arr[right];
    left++;
    right--;
}
Console.WriteLine(sum);

medium

A. 21

B. 18

C. 20

D. 15

Solution

1. Step 1: Trace the loop iterations

   Pairs added: (1+6)=7, (2+5)=7, (3+4)=7; sum = 7+7+7 = 21. Loop runs while left < right, so stops after these pairs.

2. Final Answer:

   21 -> Option A

3. Quick Check:

   Sum of pairs from ends = 21 [OK]

Hint: Sum pairs from ends until pointers meet [OK]

Common Mistakes:

• Adding elements twice
• Loop running when left equals right
• Incorrect sum calculation

4. Identify the error in the following C# code using two pointers to find if array arr contains two numbers that sum to target.

int left = 0, right = arr.Length - 1;
while (left <= right) {
    int sum = arr[left] + arr[right];
    if (sum == target) return true;
    else if (sum < target) left++;
    else right--;
}
return false;

medium

A. The sum calculation is incorrect

B. The pointers should both start at 0

C. The loop condition should be left < right instead of left <= right

D. The return statements are missing a value

Solution

1. Step 1: Analyze loop condition

   Using left <= right allows pointers to be equal, causing sum of same element twice. Change to left < right to avoid using the same element twice.

2. Final Answer:

   The loop condition should be left < right instead of left <= right -> Option C

3. Quick Check:

   Pointers must not cross or equal for two distinct elements [OK]

Hint: Use left < right to avoid same element twice [OK]

Common Mistakes:

• Allowing pointers to be equal causing wrong sums
• Starting both pointers at 0
• Misplacing return statements

5. Given a sorted array arr and a number k, how can you use the two pointer technique to find if there exists a pair with sum equal to k? Choose the correct approach.

hard

A. Initialize both pointers at start; move both right until sum equals k

B. Initialize two pointers at start and end; move left pointer right if sum < k, else move right pointer left

C. Initialize two pointers at middle; move both outward until sum equals k

D. Sort the array again and use binary search for each element

Solution

1. Step 1: Set pointers and move based on sum

   Left pointer at 0, right pointer at last index. If sum < k, move left right to increase sum; if sum > k, move right left to decrease sum.

2. Final Answer:

   Initialize two pointers at start and end; move left pointer right if sum < k, else move right pointer left -> Option B

3. Quick Check:

   Two pointers adjust to reach target sum efficiently [OK]

Hint: Move pointers inward based on sum comparison [OK]

Common Mistakes:

• Starting both pointers at same side
• Moving pointers in wrong direction
• Sorting array again unnecessarily