Two Pointer Technique on Arrays in DSA C

Mental Model

Use two markers moving through the array to find pairs or conditions without checking every pair.

Analogy: Imagine two friends starting at opposite ends of a hallway, walking towards each other to find a matching pair of shoes quickly.

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

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5], find if any two numbers sum to 7

Goal: Find two numbers in the array that add up to 7 using two pointers

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 with pointers at both ends to check sums efficiently

Step 2: Calculate sum = 1 + 5 = 6, which is less than 7, move left pointer right

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

Why: Sum too small, increase sum by moving left pointer forward

Step 3: Calculate sum = 2 + 5 = 7, found target sum, stop

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

Why: Sum matches target, solution found

Result:

[1] -> [2] -> [3] -> [4] -> [5] -> null
Pair found: 2 + 5 = 7

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>

bool two_pointer_sum(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            printf("Pair found: %d + %d = %d\n", arr[left], arr[right], target);
            return true;
        } else if (sum < target) {
            left++; // increase sum by moving left pointer right
        } else {
            right--; // decrease sum by moving right pointer left
        }
    }
    printf("No pair found that sums to %d\n", target);
    return false;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    two_pointer_sum(arr, size, target);
    return 0;
}

while (left < right) {

loop until pointers meet or cross

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

calculate sum of values at pointers

if (sum == target) {

check if sum matches target

left++; // increase sum by moving left pointer right

move left pointer right to increase sum when sum too small

right--; // decrease sum by moving right pointer left

move right pointer left to decrease sum when sum too large

Output

Pair found: 2 + 5 = 7

Complexity Analysis

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

Space: O(1) because only two pointers and a few variables are used

vs Alternative: Compared to checking all pairs (O(n^2)), this is much faster by avoiding repeated checks

Edge Cases

empty array

function returns no pair found immediately

DSA C

while (left < right) {

array with one element

function returns no pair found because pointers cannot cross

DSA C

while (left < right) {

no two numbers sum to target

function prints no pair found and returns false

DSA C

printf("No pair found that sums to %d\n", target);

When to Use This Pattern

When you need to find pairs or conditions involving two elements in a sorted array, use two pointers moving inward to find answers efficiently.

Common Mistakes

Mistake: Not moving the correct pointer based on sum comparison
Fix: If sum is less than target, move left pointer right; if sum is greater, move right pointer left

Summary

Find pairs in a sorted array that meet a condition using two pointers.

Use when searching pairs or conditions in sorted arrays to reduce time.

Move pointers inward based on sum comparison to avoid checking all pairs.

Practice

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

easy

A. Use one pointer to traverse and another to store the sum.

B. Use two arrays to store elements separately.

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

D. Use two pointers to swap elements randomly.

Solution

1. Step 1: Understand the technique

   The two pointer technique involves using two indices or pointers to scan the array, often from the start and end, to solve problems efficiently.

2. Step 2: Identify the correct description

   Use two indices to traverse the array from different ends or positions simultaneously. correctly describes using two pointers to traverse the array from different ends or positions simultaneously.

3. Final Answer:

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

4. Quick Check:

   Two pointers move from different positions = A [OK]

Hint: Two pointers move from different ends or positions [OK]

Common Mistakes:

• Thinking two pointers mean two separate arrays
• Confusing pointers with storing sums
• Assuming pointers swap elements randomly

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

easy

A. int left = 0, right = n - 1;

B. int left = 1, right = n;

C. int left = n, right = 0;

D. int left = n - 1, right = 0;

Solution

1. Step 1: Understand pointer initialization

   For two pointers starting at the beginning and end of an array, left should be 0 and right should be n - 1 because array indices start at 0.

2. Step 2: Check options

   int left = 0, right = n - 1; correctly initializes left = 0 and right = n - 1. Other options have incorrect indices.

3. Final Answer:

   int left = 0, right = n - 1; -> Option A

4. Quick Check:

   Start at 0 and end at n-1 = C [OK]

Hint: Array indices start at 0, so right = n - 1 [OK]

Common Mistakes:

• Starting left at 1 instead of 0
• Setting right to n (out of bounds)
• Swapping left and right initialization

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

int arr[] = {1, 3, 5, 7, 9};
int left = 0, right = 4;
int sum = 0;
while (left < right) {
    sum += arr[left] + arr[right];
    left++;
    right--;
}
printf("%d", sum);

medium

A. 25

B. 15

C. 30

D. 20

Solution

1. Step 1: Trace the loop iterations

   Initial pointers: left=0, right=4
   Iteration 1: sum=0+(1+9)=10, left=1, right=3
   Iteration 2: sum=10+(3+7)=20, left=2, right=2
   Loop ends because left is not less than right.

2. Step 2: Calculate final sum

   Sum after loop = 20. Note that the middle element (index 2) is not added because left == right stops the loop.

3. Final Answer:

   20 -> Option D

4. Quick Check:

   Sum pairs (1+9)+(3+7) = 20 [OK]

Hint: Sum pairs while left < right, middle element skipped [OK]

Common Mistakes:

• Including middle element when left == right
• Adding elements twice
• Incorrect loop condition

4. Identify the error in the following code snippet that uses the two pointer technique to find if a sorted array contains two numbers that sum to a target value.

int arr[] = {2, 4, 6, 8, 10};
int left = 0, right = 4;
int target = 14;
while (left <= right) {
    int sum = arr[left] + arr[right];
    if (sum == target) {
        printf("Found");
        break;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

medium

A. The pointers left and right are initialized incorrectly.

B. The loop condition should be left < right, not left <= right.

C. The sum comparison logic is reversed.

D. The printf statement should be outside the loop.

Solution

1. Step 1: Analyze loop condition

   The loop uses left <= right, which allows pointers to meet or cross. This can cause incorrect checks or double counting.

2. Step 2: Correct loop condition

   Using left < right ensures pointers do not cross and only valid pairs are checked.

3. Final Answer:

   The loop condition should be left < right, not left <= right. -> Option B

4. Quick Check:

   Pointers must not cross: left < right [OK]

Hint: Use left < right to avoid pointer crossing [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Swapping pointer increment/decrement logic
• Incorrect pointer initialization

5. Given a sorted array arr of size n, how can you use the two pointer technique to find all unique pairs that sum to a target value t? Choose the best approach.

hard

A. Initialize two pointers at start and end; move pointers inward based on sum comparison; skip duplicates to find unique pairs.

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

C. Sort the array and use binary search for each element to find complement.

D. Initialize both pointers at start and move both forward to find pairs.

Solution

1. Step 1: Use two pointers at array ends

   Start with left = 0 and right = n - 1. Calculate sum of elements at these pointers.

2. Step 2: Move pointers and skip duplicates

   If sum equals target, record pair and move both pointers skipping duplicates. If sum < target, move left pointer right. If sum > target, move right pointer left.

3. Final Answer:

   Initialize two pointers at start and end; move pointers inward based on sum comparison; skip duplicates to find unique pairs. -> Option A

4. Quick Check:

   Two pointers from ends + skip duplicates = D [OK]

Hint: Move pointers inward and skip duplicates for unique pairs [OK]

Common Mistakes:

• Using nested loops instead of two pointers
• Not skipping duplicates causing repeated pairs
• Moving both pointers forward instead of inward