Why Two Pointer Technique Beats Brute Force in DSA Javascript - 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 positions and move towards each other or in one direction, checking conditions efficiently until they meet or finish.

Execution Sample

DSA Javascript

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

Find two numbers in a sorted array that add up to 6 using two pointers moving inward.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Sum arr[left]+arr[right]	Action	Array State
1	Initialize pointers	0 (value=1)	4 (value=5)	1+5=6	Sum equals target, break loop	[1, 2, 3, 4, 5]
2	Loop ends	0	4	6	Stop searching	[1, 2, 3, 4, 5]

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

Variable Tracker

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

Key Moments - 3 Insights

Why do we move only one pointer at a time instead of both?

Because moving both pointers at once might skip potential pairs. The execution_table shows we move left or right pointer based on sum comparison to target, ensuring all valid pairs are checked efficiently.

Why does the loop stop early instead of checking all pairs?

The loop stops as soon as the target sum is found (step 1 in execution_table), which saves time compared to brute force that checks every pair.

How does two pointer technique reduce time compared to brute force?

Brute force checks all pairs (O(n²)), but two pointers move inward and stop early, reducing checks to O(n), as shown by the quick loop exit in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the sum of arr[left] + arr[right] at step 1?

A 6

B 5

C 7

D 4

💡 Hint

Check the 'Sum arr[left]+arr[right]' column at step 1 in execution_table.

At which step does the loop stop searching for pairs?

A Step 2

B Step 1

C Step 3

D Step 0

💡 Hint

Look at the 'Action' column in execution_table where the loop breaks.

If the target sum was 10 instead of 6, how would the pointers move initially?

A Both pointers move simultaneously

B Right pointer moves left

C Left pointer moves right

D No pointer moves

💡 Hint

Refer to the code logic and execution_table: sum less than target moves left pointer right.

Concept Snapshot

Two Pointer Technique:
- Use two pointers at start/end or different positions
- Move pointers based on condition (e.g., sum comparison)
- Stops early when condition met
- Runs in O(n) time, better than brute force O(n²)
- Efficient for sorted arrays or linked lists

Full Transcript

The two pointer technique uses two indexes starting at different ends of a data structure, like an array. They move inward or in one direction based on a condition, such as the sum of values at these pointers. This method checks fewer pairs than brute force, which tries all pairs. For example, in the code, pointers start at positions 0 and 4 in the array [1,2,3,4,5]. The sum at these pointers is 6, matching the target, so the loop stops immediately. This saves time compared to checking every pair. The pointers move one at a time depending on whether the sum is less or greater than the target, ensuring no pairs are missed. This approach reduces time complexity from O(n²) to O(n), making it faster and more efficient.

Practice

1. What is the main advantage of the two pointer technique over brute force in array problems?

easy

A. It always sorts the array before processing

B. It uses more memory to store intermediate results

C. It reduces time complexity by avoiding nested loops

D. It requires recursion to work properly

Solution

1. Step 1: Understand brute force time complexity

   Brute force often uses nested loops, leading to O(n²) time complexity.

2. Step 2: Analyze two pointer technique efficiency

   Two pointers move through the array in a single pass, reducing time complexity to O(n).

3. Final Answer:

   It reduces time complexity by avoiding nested loops -> Option C

4. Quick Check:

   Two pointer = faster than brute force [OK]

Hint: Two pointers scan once, brute force scans twice [OK]

Common Mistakes:

• Thinking two pointer uses more memory
• Assuming two pointer always sorts array
• Believing recursion is required

2. Which of the following is the correct syntax to initialize two pointers at the start and end of an array arr in JavaScript?

easy

A. const left = 0, right = arr.length - 1;

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

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

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

Solution

1. Step 1: Identify valid pointer initialization

   Pointers should be indices, so left = 0 and right = arr.length - 1 are correct.

2. Step 2: Check invalid options

   Options B, C, and D use incorrect indices or values outside array bounds.

3. Final Answer:

   const left = 0, right = arr.length - 1; -> Option A

4. Quick Check:

   Start at 0 and end at length-1 [OK]

Hint: Array indices start at 0, end at length-1 [OK]

Common Mistakes:

• Using arr.length as index (out of bounds)
• Starting pointers at wrong indices
• Confusing values with indices

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

const arr = [1, 2, 3, 4, 5];
let left = 0, right = arr.length - 1;
let sumPairs = [];
while (left < right) {
  sumPairs.push(arr[left] + arr[right]);
  left++;
  right--;
}
console.log(sumPairs);

medium

A. [6, 6, 6]

B. [6, 6]

C. [5, 7, 9]

D. [1, 5]

Solution

1. Step 1: Trace pointer movements and sums

   Pairs: (1+5)=6, (2+4)=6, (3+3) stops because left == right, so only two pairs added.

2. Step 2: Check loop condition and sums stored

   Loop runs while left < right, so only two sums are pushed: [6, 6].

3. Final Answer:

   [6, 6] -> Option B

4. Quick Check:

   Sum pairs from ends = [6, 6] [OK]

Hint: Two pointers meet in middle, sum pairs once [OK]

Common Mistakes:

• Including middle element sum when pointers meet
• Miscounting number of pairs
• Confusing pointer update order

4. Identify the bug in the following two pointer code that tries to find if a pair sums to 10:

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

medium

A. Loop condition should be left < right

B. Left pointer should decrement, not increment

C. Array is not sorted

D. Right pointer should decrement, not increment

Solution

1. Step 1: Analyze pointer updates

   If sum is greater than 10, right pointer should move left (decrement) to reduce sum, not increment.

2. Step 2: Check loop condition and array

   Loop condition is fine; array is sorted; only pointer update is wrong.

3. Final Answer:

   Right pointer should decrement, not increment -> Option D

4. Quick Check:

   Decrease right pointer to reduce sum [OK]

Hint: Decrease right pointer when sum too big [OK]

Common Mistakes:

• Incrementing right pointer instead of decrementing
• Changing loop condition unnecessarily
• Ignoring array sorting requirement

5. Given a sorted array arr and a target sum k, which approach best finds all unique pairs that sum to k efficiently?

Choose the best method that beats brute force.

hard

A. Use two pointers starting at both ends, move inward based on sum comparison

B. Use nested loops to check every pair for sum equals k

C. Sort the array and use binary search for each element's complement

D. Use a hash map to store elements and check complements in one pass

Solution

1. Step 1: Compare approaches for efficiency

   Nested loops (B) are O(n²), binary search (C) is O(n log n), hash map (A) is O(n) but uses extra space.

2. Step 2: Two pointer technique advantage

   Two pointers (D) scan array once in O(n) time with O(1) space, ideal for sorted arrays.

3. Final Answer:

   Use two pointers starting at both ends, move inward based on sum comparison -> Option A

4. Quick Check:

   Two pointer = best for sorted arrays [OK]

Hint: Two pointers scan once, no extra space needed [OK]

Common Mistakes:

• Choosing nested loops despite inefficiency
• Ignoring space complexity of hash map
• Using binary search unnecessarily