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

Concept Flow - Why Two Pointer Technique Beats Brute Force

Start with two pointers

↓

Check condition with pointers

↓

If condition met

→Move one pointer to narrow search

↓

Else

→Move other pointer to narrow search

↓

Repeat until pointers meet

↓

End: Result found or no solution

Two pointers start at different ends and move inward based on conditions, reducing unnecessary checks compared to brute force.

Execution Sample

DSA C++

int left = 0, right = n - 1;
while (left < right) {
  if (condition) right--;
  else left++;
}

This code moves two pointers inward to find a condition without checking all pairs.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Action Taken	Visual State
1	Initialize pointers	0	5	Start	[L=0, ..., R=5]
2	Check condition arr[L] + arr[R] > target	0	5	Condition true, move right--	[L=0, ..., R=4]
3	Check condition arr[L] + arr[R] > target	0	4	Condition false, move left++	[L=1, ..., R=4]
4	Check condition arr[L] + arr[R] > target	1	4	Condition true, move right--	[L=1, ..., R=3]
5	Check condition arr[L] + arr[R] > target	1	3	Condition false, move left++	[L=2, ..., R=3]
6	Check condition arr[L] + arr[R] > target	2	3	Pointers meet or cross, stop	[L=2, R=3]

💡 Pointers meet or cross, no more pairs to check

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
left	0	0	1	1	2	2	2
right	5	4	4	3	3	3	3

Key Moments - 3 Insights

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

Because moving one pointer narrows the search space logically based on the condition, as shown in steps 2-5 in the execution_table.

Why does the loop stop when pointers meet or cross?

When pointers meet or cross (step 6), all pairs have been checked without repetition, so continuing would be redundant.

How does this technique reduce the number of checks compared to brute force?

Brute force checks all pairs (n^2), but two pointers move inward linearly (n steps), as seen by pointer movements in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of the left pointer?

A 0

B 4

C 1

D 5

💡 Hint

Check the 'Left Pointer' column in execution_table row for step 3.

At which step do the pointers meet or cross, ending the loop?

A Step 5

B Step 6

C Step 4

D Step 2

💡 Hint

Look at the 'Action Taken' column in execution_table for when pointers meet or cross.

If the condition was always false, which pointer would move each time?

A Left pointer moves

B Both pointers move simultaneously

C Right pointer moves

D Neither pointer moves

💡 Hint

Refer to the 'Action Taken' column where condition false leads to left++.

Concept Snapshot

Two Pointer Technique:
- Use two pointers at start and end
- Move pointers inward based on condition
- Avoids checking all pairs (O(n) vs O(n^2))
- Stops when pointers meet or cross
- Efficient for sorted arrays or linear scans

Full Transcript

The two pointer technique uses two indexes starting at opposite ends of a data structure. At each step, it checks a condition involving elements at these pointers. Depending on the result, it moves one pointer inward to narrow the search space. This continues until the pointers meet or cross, ensuring all relevant pairs are checked without repetition. This approach reduces the number of checks from quadratic to linear time compared to brute force. The execution table shows pointer positions and actions at each step, and the variable tracker records pointer movements. Key moments clarify why only one pointer moves at a time and why the loop ends when pointers meet.

Practice

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

easy

A. It requires recursion to work properly

B. It uses more memory to store intermediate results

C. It always sorts the array before processing

D. It reduces time complexity by avoiding nested loops

Solution

1. Step 1: Understand brute force approach

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

2. Step 2: Analyze two pointer technique

   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 D

4. Quick Check:

   Two pointer = faster than brute force [OK]

Hint: Two pointers scan array once, avoiding double loops [OK]

Common Mistakes:

• Thinking two pointer always sorts array
• Assuming two pointer uses more memory
• Confusing recursion with two pointer

2. Which of the following is the correct syntax to initialize two pointers at the start and end of a vector v in C++?

easy

A. int left = 1, right = v.size();

B. int left = 0, right = v.size() - 1;

C. int left = v.size(), right = 0;

D. int left = -1, right = v.size() + 1;

Solution

1. Step 1: Understand vector indexing

   Vectors in C++ are zero-indexed, so first element is at 0 and last at size()-1.

2. Step 2: Check pointer initialization

   Setting left = 0 and right = v.size() - 1 correctly points to start and end.

3. Final Answer:

   int left = 0, right = v.size() - 1; -> Option B

4. Quick Check:

   Start=0, End=size()-1 [OK]

Hint: Start pointer at 0, end pointer at size()-1 [OK]

Common Mistakes:

• Starting pointers at 1 instead of 0
• Using size() as index (out of range)
• Negative or invalid pointer initialization

3. What is the output of the following C++ code snippet using two pointers?

std::vector<int> v = {1, 2, 3, 4, 5};
int left = 0, right = 4;
while (left < right) {
  std::cout << v[left] + v[right] << " ";
  left++;
  right--;
}

medium

A. 6 6

B. 5 7 9

C. 1 2 3 4 5

D. 9 7 5

Solution

1. Step 1: Trace pointer values and sums

   Pairs: v[0]+v[4]=1+5=6, v[1]+v[3]=2+4=6, then left=2, right=2 (loop stops since left < right is false).

2. Step 2: Output sums until pointers meet

   Outputs are 6 6.

3. Final Answer:

   6 6 -> Option A

4. Quick Check:

   Sum pairs from ends = 6 6 [OK]

Hint: Sum elements at left and right pointers until they meet [OK]

Common Mistakes:

• Including sum when pointers are equal
• Confusing pointer increments
• Printing elements instead of sums

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

std::vector<int> v = {1, 3, 5, 7, 9};
int left = 0, right = v.size() - 1;
while (left < right) {
  if (v[left] + v[right] == 10) {
    std::cout << "Found";
    break;
  } else if (v[left] + v[right] > 10) {
    left++;
  } else {
    right--;
  }
}

medium

A. Loop condition should be left <= right

B. Vector is not sorted before two pointer use

C. Pointers are moved in wrong directions for sum comparison

D. Output statement is missing a newline

Solution

1. Step 1: Understand pointer movement logic

   If sum > 10, we should move right pointer left to reduce sum, not left pointer right.

2. Step 2: Identify correct pointer moves

   Correct moves: if sum > target, right-- ; if sum < target, left++.

3. Final Answer:

   Pointers are moved in wrong directions for sum comparison -> Option C

4. Quick Check:

   Sum > target -> move right pointer left [OK]

Hint: Move right pointer left if sum too big, left pointer right if too small [OK]

Common Mistakes:

• Swapping pointer moves for sum comparisons
• Using wrong loop condition
• Ignoring vector sorting requirement

5. Given a sorted array arr = {1, 2, 3, 4, 5, 6, 7}, how can the two pointer technique be used to find all pairs that sum to 8 efficiently?

hard

A. Initialize pointers at start and end, move inward adjusting based on sum

B. Use nested loops to check all pairs for sum 8

C. Sort the array first, then use binary search for each element

D. Use recursion to check pairs from both ends

Solution

1. Step 1: Initialize two pointers

   Set left pointer at index 0 and right pointer at last index (6).

2. Step 2: Move pointers based on sum comparison

   If sum of elements at pointers is less than 8, move left pointer right; if more, move right pointer left; if equal, record pair and move both pointers.

3. Step 3: Continue until pointers cross

   Stop when left pointer is no longer less than right pointer.

4. Final Answer:

   Initialize pointers at start and end, move inward adjusting based on sum -> Option A

5. Quick Check:

   Two pointer moves inward checking sums [OK]

Hint: Start ends, move pointers inward based on sum comparison [OK]

Common Mistakes:

• Using nested loops instead of two pointers
• Not moving pointers correctly after finding a pair
• Sorting array unnecessarily when already sorted