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

Concept Flow - Why Two Pointer Technique Beats Brute Force

Start with two pointers

↓

Check condition between pointers

↓

Move pointers inward

↓

Repeat until pointers cross

↓

End

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

Execution Sample

DSA Python

arr = [1, 3, 5, 7, 9]
left = 0
right = 4
while left < right:
    if arr[left] + arr[right] == 10:
        print(left, right)
        break
    elif arr[left] + arr[right] < 10:
        left += 1
    else:
        right -= 1

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

Execution Table

Step	Operation	left	right	Sum arr[left]+arr[right]	Condition	Action	Visual State
1	Initialize pointers	0	4	1+9=10	Sum == 10	Print indices and break	[1, 3, 5, 7, 9] ^ ^
2	End	-	-	-	-	Loop ends as pair found	[1, 3, 5, 7, 9] ^ ^

💡 Found pair at indices 0 and 4 where sum equals 10, loop ends early.

Variable Tracker

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

Key Moments - 3 Insights

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

Because the array is sorted, increasing left moves to a bigger number, increasing the sum.

Why does the loop stop when left meets right?

Because pointers crossing means all pairs checked without success. In this example, loop ends early at step 1 due to finding the pair.

How does two pointer avoid checking all pairs like brute force?

Two pointer moves inward skipping impossible pairs, unlike brute force which checks every pair. This is shown by only one iteration 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 10

B 9

C 8

D 11

💡 Hint

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

At which step does the loop end because the pair is found?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look at the 'Action' column where it says 'Print indices and break' in execution_table.

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

A It would still work the same way

B It would need to check all pairs like brute force

C It would move pointers randomly

D It would only move one pointer

💡 Hint

Two pointer relies on sorted order to decide pointer moves, see key_moments explanation.

Concept Snapshot

Two Pointer Technique:
- Use two pointers at array ends
- Move pointers inward based on sum comparison
- Stops early when condition met
- Beats brute force by skipping unnecessary pairs
- Requires sorted array for correctness

Full Transcript

The two pointer technique uses two indexes starting at opposite ends of a sorted array. At each step, it checks the sum of values at these pointers. If the sum matches the target, it stops early. If the sum is less, it moves the left pointer right to increase sum. If the sum is more, it moves the right pointer left to decrease sum. This avoids checking all pairs like brute force, making it faster. The loop ends when pointers cross or pair found.

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 once, brute force scans many times [OK]

Common Mistakes:

• Thinking two pointer always sorts the array
• Confusing memory use with speed
• Assuming recursion is needed

2. Which of the following is the correct syntax to initialize two pointers at the start and end of a list named arr in Python?

easy

A. left = 0; right = len(arr) - 1

B. left = 1; right = len(arr)

C. left = len(arr); right = 0

D. left = -1; right = len(arr) + 1

Solution

1. Step 1: Identify valid indices in Python list

   Python lists start at index 0 and end at len(arr) - 1.

2. Step 2: Check pointer initialization

   Left pointer should be 0 (start), right pointer should be len(arr) - 1 (end).

3. Final Answer:

   left = 0; right = len(arr) - 1 -> Option A

4. Quick Check:

   Start = 0, End = length-1 [OK]

Hint: Start pointer at 0, end pointer at length minus one [OK]

Common Mistakes:

• Starting pointers outside valid index range
• Using 1-based indexing in Python
• Setting right pointer to len(arr) instead of len(arr)-1

3. What will be the output of the following Python code using two pointers?

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

print(two_sum_sorted([1, 3, 4, 5, 7, 10], 9))

medium

A. [0, 5]

B. [1, 3]

C. [2, 3]

D. [-1, -1]

Solution

1. Step 1: Trace the execution step-by-step

   arr = [1,3,4,5,7,10]
   left=0 (1), right=5 (10), sum=11 >9 -> right=4
   left=0 (1), right=4 (7), sum=8 <9 -> left=1
   left=1 (3), right=4 (7), sum=10 >9 -> right=3
   left=1 (3), right=3 (5), sum=8 <9 -> left=2
   left=2 (4), right=3 (5), sum=9 ==9 -> return [2, 3]

2. Final Answer:

   [2, 3] -> Option C

3. Quick Check:

   arr[2] + arr[3] = 4 + 5 = 9 [OK]

Hint: Move pointers based on sum compared to target [OK]

Common Mistakes:

• Not updating pointers correctly
• Returning wrong indices
• Confusing array values with indices

4. Find the error in this two pointer code snippet that tries to find if a pair sums to target in a sorted list:

def has_pair(arr, target):
    left, right = 0, len(arr)
    while left < right:
        if arr[left] + arr[right] == target:
            return True
        elif arr[left] + arr[right] < target:
            left += 1
        else:
            right -= 1
    return False

medium

A. left should start at 1 instead of 0

B. right should be initialized to len(arr) - 1

C. The while condition should be left <= right

D. The function should return indices instead of True/False

Solution

1. Step 1: Check pointer initialization

   right is set to len(arr), which is out of valid index range (max index is len(arr)-1).

2. Step 2: Correct pointer initialization

   right should be len(arr) - 1 to point to last element.

3. Final Answer:

   right should be initialized to len(arr) - 1 -> Option B

4. Quick Check:

   Valid indices = 0 to length-1 [OK]

Hint: Right pointer must be last valid index, not length [OK]

Common Mistakes:

• Using len(arr) as index causes IndexError
• Changing left pointer start incorrectly
• Misusing while loop condition

5. Given a sorted array arr and a target sum, how does the two pointer technique efficiently find all unique pairs that add up to the target compared to brute force?

hard

A. By moving pointers inward and skipping duplicates, it avoids checking all pairs

B. By sorting the array multiple times to find pairs quickly

C. By using nested loops to check every possible pair

D. By using recursion to split the array and find pairs

Solution

1. Step 1: Understand brute force approach

   Brute force checks every pair with nested loops, O(n²) time.

2. Step 2: Explain two pointer efficiency

   Two pointers start at ends, move inward based on sum comparison, skipping duplicates to avoid repeats, achieving O(n) time.

3. Final Answer:

   By moving pointers inward and skipping duplicates, it avoids checking all pairs -> Option A

4. Quick Check:

   Two pointer skips pairs, brute force checks all [OK]

Hint: Skip duplicates and move pointers inward for efficiency [OK]

Common Mistakes:

• Thinking sorting happens multiple times
• Confusing recursion with two pointer
• Assuming nested loops are used in two pointer