Why Two Pointer Technique Beats Brute Force in DSA Typescript - See It Work

Why Two Pointer Technique Beats Brute Force

📖 Scenario: Imagine you have a list of numbers representing the heights of people standing in a line. You want to find two people whose combined height is exactly a target number. This is like finding two friends who together reach a certain height when standing side by side.

🎯 Goal: You will build a program that finds two numbers in a sorted list that add up to a target sum. First, you will try the simple but slow way (brute force). Then, you will use the faster two pointer technique to find the answer efficiently.

📋 What You'll Learn

Create a sorted array called heights with exact values [1, 3, 4, 5, 7, 10, 12]

Create a variable called targetSum with the value 15

Write a brute force nested loop to find two numbers in heights that add up to targetSum

Write a two pointer technique to find two numbers in heights that add up to targetSum

Print the pairs found by both methods

💡 Why This Matters

🌍 Real World

Finding pairs of numbers that meet a condition is common in tasks like matching friends by height, pairing products by price, or finding compatible items.

💼 Career

Understanding two pointer technique helps in coding interviews and real-world problems where efficient searching in sorted data is needed.

1

Create the sorted array of heights

Create a sorted array called heights with these exact values: [1, 3, 4, 5, 7, 10, 12]

DSA Typescript

# Create the sorted array heights with the given values
# Your code here

Hint

Use const heights: number[] = [1, 3, 4, 5, 7, 10, 12]; to create the array.

2

Set the target sum

Create a variable called targetSum and set it to 15

DSA Typescript

const heights: number[] = [1, 3, 4, 5, 7, 10, 12];
# Create the targetSum variable and set it to 15
# Your code here

Hint

Use const targetSum: number = 15; to create the variable.

3

Write brute force nested loops to find the pair

Write nested for loops with variables i and j to check all pairs in heights. If heights[i] + heights[j] === targetSum, store the pair in a variable called bruteForcePair and break the loops.

DSA Typescript

const heights: number[] = [1, 3, 4, 5, 7, 10, 12];
const targetSum: number = 15;
// Use nested loops to find the pair that sums to targetSum
// Your code here

Hint

Use two loops: outer loop with i, inner loop with j starting from i + 1. Check if sum equals targetSum.

4

Use two pointer technique and print both results

Use two pointers left starting at 0 and right starting at heights.length - 1. Move pointers inward to find a pair that sums to targetSum. Store the pair in twoPointerPair. Then print both bruteForcePair and twoPointerPair using console.log.

DSA Typescript

const heights: number[] = [1, 3, 4, 5, 7, 10, 12];
const targetSum: number = 15;

let bruteForcePair: [number, number] | null = null;
for (let i = 0; i < heights.length; i++) {
    for (let j = i + 1; j < heights.length; j++) {
        if (heights[i] + heights[j] === targetSum) {
            bruteForcePair = [heights[i], heights[j]];
            break;
        }
    }
    if (bruteForcePair !== null) {
        break;
    }
}

// Use two pointer technique to find the pair
// Print both pairs
// Your code here

Hint

Use left and right pointers to check sums. Move left forward if sum is less than target, move right backward if sum is more. Print both pairs with console.log.

Practice

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

easy

A. It reduces the number of comparisons by moving pointers inward based on conditions.

B. It uses recursion to explore all possibilities efficiently.

C. It sorts the array first to make searching faster.

D. It uses extra memory to store intermediate results.

Solution

1. Step 1: Understand brute force approach

   Brute force checks all pairs, leading to many unnecessary comparisons.

2. Step 2: Analyze two pointer technique advantage

   Two pointers move inward based on conditions, skipping unnecessary checks and reducing time.

3. Final Answer:

   It reduces the number of comparisons by moving pointers inward based on conditions. -> Option A

4. Quick Check:

   Two pointer skips pairs, faster than brute force [OK]

Hint: Two pointers move inward to skip unnecessary checks [OK]

Common Mistakes:

• Thinking recursion is always faster
• Confusing sorting with two pointer technique
• Assuming extra memory is used in two pointer

2. Which of the following is the correct syntax to initialize two pointers in TypeScript for an array named arr?

easy

A. let left = arr[0], right = arr[arr.length];

B. let left = 0, right = arr.length - 1;

C. let left = 1, right = arr.length;

D. let left = arr.length, right = 0;

Solution

1. Step 1: Identify valid pointer indices

   Array indices start at 0 and end at length - 1.

2. Step 2: Check each option

   let left = 0, right = arr.length - 1; correctly sets left to 0 and right to last index (length - 1). Others use invalid indices.

3. Final Answer:

   let left = 0, right = arr.length - 1; -> Option B

4. Quick Check:

   Array indices start at 0 [OK]

Hint: Array indices go from 0 to length-1 [OK]

Common Mistakes:

• Starting pointer at 1 instead of 0
• Using arr.length as index (out of bounds)
• Swapping left and right pointers

3. Consider the following TypeScript code using two pointers to find if a sorted array contains two numbers that sum to 10:

const arr = [1, 2, 3, 7, 8, 9];
let left = 0;
let right = arr.length - 1;
let found = false;
while (left < right) {
  const sum = arr[left] + arr[right];
  if (sum === 10) {
    found = true;
    break;
  } else if (sum < 10) {
    left++;
  } else {
    right--;
  }
}
console.log(found);

What will be printed?

medium

A. Error

B. false

C. undefined

D. true

Solution

1. Step 1: Trace pointer values and sums

   Start: left=0(arr[0]=1), right=5(arr[5]=9), sum=10 -> found=true, loop breaks.

2. Step 2: Confirm output

   Since found is set to true, console.log prints true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   1 + 9 = 10 found [OK]

Hint: Check sum at pointers, move accordingly [OK]

Common Mistakes:

• Not breaking loop after finding sum
• Confusing pointer increments
• Assuming array is unsorted

4. The following TypeScript code tries to find two numbers in a sorted array that sum to 15 using two pointers, but it has a bug:

const arr = [2, 4, 6, 8, 10];
let left = 0;
let right = arr.length;
let found = false;
while (left < right) {
  const sum = arr[left] + arr[right];
  if (sum === 15) {
    found = true;
    break;
  } else if (sum < 15) {
    left++;
  } else {
    right--;
  }
}
console.log(found);

What is the bug?

medium

A. right pointer is initialized out of array bounds

B. left pointer should start at 1

C. sum comparison should be with 10 instead of 15

D. The loop condition should be left <= right

Solution

1. Step 1: Check pointer initialization

   right is set to arr.length which is out of bounds (max index is length - 1).

2. Step 2: Understand impact of bug

   Accessing arr[right] causes runtime error or undefined behavior.

3. Final Answer:

   right pointer is initialized out of array bounds -> Option A

4. Quick Check:

   Array indices max is length-1 [OK]

Hint: Right pointer must be length - 1, not length [OK]

Common Mistakes:

• Starting left pointer at 1
• Changing sum target incorrectly
• Using <= instead of < in loop

5. You have a sorted array arr = [1, 3, 4, 5, 7, 10, 12]. Using the two pointer technique, how many unique pairs sum to 13?

hard

A. 4

B. 3

C. 2

D. 1

Solution

1. Step 1: Initialize pointers and check sums

   left=0(arr[0]=1), right=6(arr[6]=12), sum=13 -> count=1, move left++ and right--

2. Step 2: Continue checking pairs

   left=1(arr[1]=3), right=5(arr[5]=10), sum=13 -> count=2, move left++ and right--

3. Step 3: Check next pair

   left=2(arr[2]=4), right=4(arr[4]=7), sum=11 < 13 -> move left++

4. Step 4: Check final pair

   left=3(arr[3]=5), right=4(arr[4]=7), sum=12 < 13 -> move left++

5. Step 5: Pointers crossed, stop

   Total pairs found = 2

6. Final Answer:

   2 -> Option C

7. Quick Check:

   Pairs (1,12) and (3,10) sum to 13 [OK]

Hint: Move pointers inward, count pairs summing to target [OK]

Common Mistakes:

• Counting pairs with same elements twice
• Not moving pointers correctly after sum check
• Assuming pairs must be adjacent