Why Two Pointer Technique Beats Brute Force in DSA Go - Why This Pattern

Mental Model

Two pointers move through data to find answers faster by avoiding repeated work. Instead of checking everything again and again, they work together to cover the data efficiently.

Analogy: Imagine two friends walking along a line of houses to find pairs that match a rule. Instead of one friend checking every house with every other house (slow), they start at opposite ends and move inward, quickly finding pairs without repeating checks.

Start:
[left->] 1 -> 2 -> 3 -> 4 -> 5 [←right]
Pointers at ends moving towards center

Dry Run Walkthrough

Input: array: [1, 2, 3, 4, 5], find two numbers that sum to 6

Goal: Find a pair of numbers that add up to 6 using two pointers faster than checking all pairs

Step 1: Set left pointer at index 0 (value 1), right pointer at index 4 (value 5)

[left->1] -> 2 -> 3 -> 4 -> [5←right]

Why: Start pointers at both ends to check sums from extremes

Step 2: Calculate sum: 1 + 5 = 6, found target sum

[left->1] -> 2 -> 3 -> 4 -> [5←right]

Why: Sum matches target, so we found the pair without checking all pairs

Result:

[1←left] -> 2 -> 3 -> 4 -> [5->right]
Pair found: (1, 5)

Annotated Code

DSA Go

package main

import "fmt"

func twoPointerSum(arr []int, target int) (int, int) {
    left, right := 0, len(arr)-1
    for left < right {
        sum := arr[left] + arr[right]
        if sum == target {
            return arr[left], arr[right] // found pair
        } else if sum < target {
            left++ // increase sum by moving left pointer right
        } else {
            right-- // decrease sum by moving right pointer left
        }
    }
    return -1, -1 // no pair found
}

func main() {
    arr := []int{1, 2, 3, 4, 5}
    target := 6
    a, b := twoPointerSum(arr, target)
    if a != -1 {
        fmt.Printf("Pair found: (%d, %d)\n", a, b)
    } else {
        fmt.Println("No pair found")
    }
}

left, right := 0, len(arr)-1

initialize two pointers at array ends

for left < right {

loop until pointers meet

sum := arr[left] + arr[right]

calculate sum of values at pointers

if sum == target { return arr[left], arr[right] }

found target sum, return pair

else if sum < target { left++ }

sum too small, move left pointer right to increase sum

else { right-- }

sum too big, move right pointer left to decrease sum

Output

Pair found: (1, 5)

Complexity Analysis

Time: O(n) because each pointer moves at most n steps through the array once

Space: O(1) because only two pointers and a few variables are used

vs Alternative: Brute force checks all pairs with O(n²) time, which is much slower for large arrays

Edge Cases

empty array

returns no pair found immediately

DSA Go

left, right := 0, len(arr)-1

array with one element

returns no pair found because left is not less than right

DSA Go

for left < right {

no pair sums to target

loop ends without finding pair, returns (-1, -1)

DSA Go

return -1, -1

When to Use This Pattern

When you need to find pairs or subarrays with certain sums or conditions in sorted data, use two pointers to move inward from both ends to reduce repeated checks and improve speed.

Common Mistakes

Mistake: Moving both pointers at the same time without checking sum comparison
Fix: Move only one pointer based on whether sum is less or greater than target

Mistake: Not sorting the array before applying two pointers
Fix: Ensure array is sorted so that moving pointers adjusts sums predictably

Summary

It finds pairs in sorted data efficiently by moving two pointers from ends toward center.

Use it when searching pairs or subarrays with conditions in sorted arrays to avoid slow nested loops.

The key insight is that moving pointers based on sum comparison skips unnecessary checks and speeds up search.

Practice

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

easy

A. It reduces time complexity by avoiding nested loops

B. It uses more memory to store intermediate results

C. It always sorts the array first

D. It requires recursion to work

Solution

1. Step 1: Understand brute force approach

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

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 A

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 array
• Confusing memory use with speed
• Assuming recursion is needed

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

easy

A. left, right := 1, len(arr)

B. left, right := 0, len(arr)-1

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

D. left, right := -1, len(arr)-1

Solution

1. Step 1: Check Go syntax for multiple assignment

   Go allows multiple variables to be assigned with := like left, right := 0, len(arr)-1.

2. Step 2: Validate pointer positions

   Left pointer starts at 0 (start), right pointer at len(arr)-1 (end).

3. Final Answer:

   left, right := 0, len(arr)-1 -> Option B

4. Quick Check:

   Initialize pointers at array ends [OK]

Hint: Start pointers at 0 and last index [OK]

Common Mistakes:

• Using len(arr) as index (out of range)
• Starting left pointer at 1 instead of 0
• Using assignment without := in declaration

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

arr := []int{1, 3, 5, 7, 9}
left, right := 0, len(arr)-1
sum := 0
for left <= right {
  sum += arr[left] + arr[right]
  left++
  right--
}
fmt.Println(sum)

medium

A. 50

B. Error

C. 25

D. 30

Solution

1. Step 1: Trace pointer movements and sums

   Pairs added: (1+9)=10, (3+7)=10, (5+5)=10; sum = 10+10+10 = 30 but note middle element added twice.

2. Step 2: Check loop condition and sum calculation

   Loop runs while left <= right, so middle element 5 is added twice, sum = 10 + 10 + 10 = 30.

3. Final Answer:

   25 -> Option C

4. Quick Check:

   Sum pairs including middle twice = 25 [OK]

Hint: Sum pairs until pointers cross, middle counted twice [OK]

Common Mistakes:

• Counting middle element once only
• Stopping loop before left equals right
• Assuming error due to pointers

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

arr := []int{2, 4, 6, 8}
left, right := 0, len(arr)-1
for left < right {
  if arr[left]+arr[right] == 10 {
    fmt.Println("Found")
    break
  } else if arr[left]+arr[right] < 10 {
    right--
  } else {
    left++
  }
}

medium

A. Loop condition should be left <= right

B. Missing initialization of pointers

C. Array is not sorted

D. Pointers move in wrong directions for sum comparison

Solution

1. Step 1: Understand pointer movement logic

   If sum < 10, we should increase left pointer to get larger sum, not decrease right.

2. Step 2: Identify incorrect pointer updates

   Code decreases right pointer when sum < 10, which reduces sum further, causing infinite loop or wrong result.

3. Final Answer:

   Pointers move in wrong directions for sum comparison -> Option D

4. Quick Check:

   Increase left if sum too small, decrease right if too big [OK]

Hint: Increase left for bigger sum, decrease right for smaller sum [OK]

Common Mistakes:

• Swapping pointer moves for sum comparison
• Using wrong loop condition
• Ignoring array sorting requirement

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

hard

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

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

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

D. Use recursion to find pairs summing to 10

Solution

1. Step 1: Initialize pointers at array ends

   Set left = 0 and right = len(arr)-1 to start checking pairs from both ends.

2. Step 2: Move pointers based on sum

   If sum of arr[left] + arr[right] is less than 10, move left pointer right to increase sum; if more, move right pointer left to decrease sum.

3. Step 3: Collect pairs when sum equals 10

   When sum equals 10, record the pair and move both pointers inward to find other pairs.

4. Final Answer:

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

5. Quick Check:

   Two pointer scan finds pairs in O(n) [OK]

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

Common Mistakes:

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