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

Concept Flow - Why Two Pointer Technique Beats Brute Force

Start with two pointers

↓

Check condition between pointers

↓

Move pointers

↓

Repeat until pointers meet

Two pointers start at different ends and move towards each other, checking conditions efficiently without nested loops.

Execution Sample

DSA Typescript

const arr = [1, 3, 5, 7, 9];
let left = 0;
let right = arr.length - 1;
while (left < right) {
  if (arr[left] + arr[right] === 10) {
    break;
  } else if (arr[left] + arr[right] < 10) {
    left++;
  } else {
    right--;
  }
}

Find two numbers in a sorted array that sum to 10 using two pointers moving inward.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Sum	Action	Visual State
1	Initialize pointers and check sum	0 (value=1)	4 (value=9)	1+9=10	Sum equals target, break loop	[1] -> 3 -> 5 -> 7 -> [9]
2	Loop ends	0	4	10	Exit loop	[1] -> 3 -> 5 -> 7 -> [9]

💡 Sum equals target at step 1, loop breaks early without checking all pairs.

Variable Tracker

Variable	Start	After Step 1	After Step 2 (End)
left	0	0	0
right	4	4	4

Key Moments - 3 Insights

Why does the two pointer method stop early instead of checking all pairs?

Because at step 1 in the execution_table, the sum matches the target, so the loop breaks early, avoiding unnecessary checks.

Why do we move the left pointer forward when the sum is less than the target?

Because the array is sorted, increasing the left pointer moves to a larger number, increasing the sum, as shown in the code and execution_table.

How does two pointer technique avoid nested loops unlike brute force?

It uses two pointers moving inward in a single loop, as shown in the concept_flow, instead of checking every pair with nested loops.

Visual Quiz - 3 Questions

Look at the execution_table, what is the sum at step 1?

A 8

B 9

C 10

D 11

💡 Hint

Check the 'Sum' column in the first row of execution_table.

At which step does the loop break because the sum equals the target?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Action' column in execution_table rows.

If the array was not sorted, how would the two pointer technique change?

A It would still work the same way.

B It would not guarantee correct results without sorting.

C Pointers would move randomly.

D We would only move the right pointer.

💡 Hint

Recall the explanation in key_moments about why sorting is important for pointer movement.

Concept Snapshot

Two Pointer Technique:
- Use two pointers at array ends
- Move pointers inward based on condition
- Avoid nested loops
- Works best on sorted arrays
- Beats brute force by reducing checks

Full Transcript

The two pointer technique uses two pointers starting at opposite ends of a sorted array. They move inward checking sums or conditions. When the sum matches the target, the loop breaks early, avoiding checking all pairs like brute force. This reduces time complexity from quadratic to linear. The pointers move based on whether the sum is less or greater than the target, leveraging the sorted order. This method is efficient and simple, beating brute force by skipping unnecessary checks.

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