Why Two Pointer Technique Beats Brute Force in DSA C - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Two Pointer Sum Check

What is the output of the following C code that uses two pointers to find if a pair sums to 10?

DSA C

#include <stdio.h>

int main() {
    int arr[] = {1, 2, 3, 7, 8, 9};
    int left = 0, right = 5;
    int target = 10;
    int found = 0;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            found = 1;
            break;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    if (found) {
        printf("Pair found: %d + %d = %d\n", arr[left], arr[right], target);
    } else {
        printf("No pair found\n");
    }
    return 0;
}

A Pair found: 1 + 9 = 10

B Pair found: 2 + 8 = 10

C Pair found: 3 + 7 = 10

D No pair found

💡 Hint

Trace the pointers moving inward and check sums.

The two pointer technique starts with left at 0 and right at 5. Sum of arr[0]+arr[5] = 1+9=10 matches target, so the code breaks immediately. The code finds the first pair that sums to 10, which is 1+9=10. So option A is correct.

🧠 Conceptual

intermediate

Why Two Pointer Technique is Faster than Brute Force

Which of the following best explains why the two pointer technique is faster than brute force for sorted arrays?

A It uses extra memory to store sums for quick lookup.

B It uses nested loops to check all pairs, reducing time complexity.

C It moves pointers inward based on sum comparison, avoiding unnecessary checks.

D It sorts the array first, then uses binary search for each element.

💡 Hint

Think about how the pointers move and reduce checks.

The two pointer technique uses two indices moving inward from both ends. It compares sums and moves pointers to skip unnecessary pairs, reducing time complexity from O(n^2) to O(n).

🔧 Debug

advanced

Find the Bug in Two Pointer Implementation

What error does the following code produce when trying to find a pair summing to 15 in a sorted array?

DSA C

#include <stdio.h>

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int left = 0, right = 4;
    int target = 15;
    int found = 0;
    while (left <= right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            found = 1;
            break;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    if (found) {
        printf("Pair found: %d + %d = %d\n", arr[left], arr[right], target);
    } else {
        printf("No pair found\n");
    }
    return 0;
}

A Runs correctly and prints 'Pair found: 6 + 9 = 15'

B Segmentation fault due to invalid array access

C Runs infinitely due to wrong loop condition

D Runs correctly and prints 'No pair found'

💡 Hint

Check the loop condition and array values carefully.

The loop condition uses left <= right, which is valid. The array has no pair summing to 15, so it prints 'No pair found'. No infinite loop or segmentation fault occurs.

🚀 Application

advanced

Using Two Pointer to Remove Duplicates in Sorted Array

Given a sorted array, which code snippet correctly removes duplicates in-place and returns the new length?

A

int removeDuplicates(int* nums, int numsSize) {
    int i = 0;
    for (int j = 0; j < numsSize; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

B

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    int i = 0;
    for (int j = 1; j < numsSize; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

C

int removeDuplicates(int* nums, int numsSize) {
    int i = 0;
    for (int j = 1; j <= numsSize; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i;
}

D

int removeDuplicates(int* nums, int numsSize) {
    int i = 1;
    for (int j = 0; j < numsSize; j++) {
        if (nums[j] != nums[i]) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

💡 Hint

Check loop bounds and initial indices carefully.

Option B correctly uses two pointers i and j, starts i at 0, j at 1, and updates i and array when a new unique element is found. It returns i+1 as the new length.

🧠 Conceptual

expert

Time Complexity Comparison of Two Pointer vs Brute Force

What is the time complexity of the two pointer technique compared to brute force when finding pairs in a sorted array?

A Two pointer: O(n), Brute force: O(n^2)

B Two pointer: O(n^2), Brute force: O(n)

C Two pointer: O(log n), Brute force: O(n log n)

D Two pointer: O(n log n), Brute force: O(n^2)

💡 Hint

Consider how many times each pointer moves in two pointer approach.

Two pointer technique moves each pointer at most n times, resulting in O(n) time. Brute force checks all pairs, O(n^2).

Practice

1. Why does the two pointer technique often perform better than brute force in problems involving arrays or strings?

easy

A. Because it uses extra memory to store intermediate results.

B. Because it uses recursion to explore all possibilities.

C. Because it sorts the array first to make searching faster.

D. Because it reduces the number of nested loops by using two indices moving towards each other or in one direction.

Solution

1. Step 1: Understand brute force approach

   Brute force often uses nested loops to check all pairs or combinations, leading to higher time complexity.

2. Step 2: Analyze two pointer technique advantage

   Two pointers use two indices that move intelligently, avoiding unnecessary checks and reducing complexity.

3. Final Answer:

   Because it reduces the number of nested loops by using two indices moving towards each other or in one direction. -> Option D

4. Quick Check:

   Two pointers reduce nested loops = A [OK]

Hint: Two pointers move smartly to avoid nested loops [OK]

Common Mistakes:

• Thinking two pointers always require sorting
• Confusing two pointers with recursion
• Assuming extra memory is always used

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 = 1, right = n;

B. int left = n, right = 0;

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

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

Solution

1. Step 1: Identify valid pointer initialization

   For two pointers at array ends, left starts at 0 and right at n-1 (last index).

2. Step 2: Check each option

   int left = 0, right = n - 1; correctly sets left=0 and right=n-1. Others have invalid indices out of range.

3. Final Answer:

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

4. Quick Check:

   Array indices start at 0, last index is n-1 = B [OK]

Hint: Start left at 0 and right at n-1 for array ends [OK]

Common Mistakes:

• Starting indices at 1 instead of 0
• Setting right pointer beyond array size
• Swapping left and right initialization

3. What is the output of the following C code snippet using two pointers to find if a sorted array contains two numbers that sum to 9?

int arr[] = {1, 2, 4, 4, 5, 6};
int left = 0, right = 5;
int found = 0;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == 9) {
        found = 1;
        break;
    } else if (sum < 9) {
        left++;
    } else {
        right--;
    }
}
printf("%d\n", found);

medium

A. 1

B. 0

C. 6

D. Compilation error

Solution

1. Step 1: Trace the two pointer movement

   Start left=0 (1), right=5 (6), sum=7 < 9, move left to 1 (2). Then sum=2+6=8 < 9, left=2 (4). Sum=4+6=10 > 9, right=4 (5). Sum=4+5=9 found!

2. Step 2: Confirm found flag and output

   Since sum==9 found, found=1 and loop breaks. printf prints 1.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   Two pointers find sum 9 = 1 [OK]

Hint: Move pointers based on sum compared to target [OK]

Common Mistakes:

• Not updating pointers correctly
• Confusing sum comparison logic
• Assuming array is unsorted

4. The following code attempts to find if any two numbers in a sorted array sum to 10 using two pointers. What is the bug?

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

medium

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

B. The sum comparison should be with 9, not 10.

C. The pointers should start at left=1 and right=3.

D. The array must be unsorted for two pointer to work.

Solution

1. Step 1: Analyze loop condition

   Using left <= right allows pointers to be equal, causing sum of same element twice, which is invalid for two distinct elements.

2. Step 2: Correct loop condition

   Changing to left < right ensures pointers do not cross or point to same element, avoiding incorrect sums.

3. Final Answer:

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

4. Quick Check:

   Loop must stop before pointers meet = C [OK]

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

Common Mistakes:

• Allowing pointers to be equal in loop
• Changing target sum incorrectly
• Starting pointers inside array instead of ends

5. Given a sorted array of integers, how can the two pointer technique be adapted to find all unique pairs that sum to a target value without duplicates? Choose the best approach.

hard

A. Use a hash map to store counts and ignore two pointer technique.

B. Use two pointers and skip duplicate values by moving pointers past equal elements after finding a pair.

C. Sort the array again after each pair is found to remove duplicates.

D. Use nested loops to check all pairs and store pairs in a set to avoid duplicates.

Solution

1. Step 1: Understand duplicate pairs problem

   When array has repeated elements, two pointer may find same pair multiple times.

2. Step 2: Skip duplicates after finding a pair

   After finding a pair, move left pointer forward while next element equals current, and similarly move right pointer backward while next equals current, to avoid duplicates.

3. Final Answer:

   Use two pointers and skip duplicate values by moving pointers past equal elements after finding a pair. -> Option B

4. Quick Check:

   Skip duplicates by advancing pointers after pair found = D [OK]

Hint: Skip duplicates by moving pointers past equal elements [OK]

Common Mistakes:

• Re-sorting array repeatedly
• Using nested loops instead of two pointers
• Ignoring duplicates causing repeated pairs