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