Two Pointer Technique on Arrays in DSA Go - Deep Dive

Overview - Two Pointer Technique on Arrays

What is it?

The Two Pointer Technique on Arrays is a way to solve problems by using two markers that move through the array. These pointers help find pairs, subarrays, or conditions without checking every element against every other. It makes some problems faster and easier to solve. Instead of nested loops, you move pointers based on conditions.

Why it matters

Without this technique, many array problems would require slow methods that check all pairs or combinations, making programs take too long. The two pointer method speeds up these tasks, saving time and computing power. This is important in real-world apps like searching, sorting, or matching data quickly.

Where it fits

Before learning this, you should understand arrays and basic loops. After this, you can learn sliding window techniques and more advanced array algorithms like binary search on sorted arrays.

Mental Model

Core Idea

Use two markers moving through the array to find answers efficiently by narrowing down possibilities step-by-step.

Think of it like...

Imagine two people walking towards each other on a path, looking for a meeting point that satisfies a condition, adjusting their speed or direction based on what they see.

Array: [a0, a1, a2, ..., an-1]
Pointers:  p1          p2

Start: p1 at index 0, p2 at index n-1
Move p1 forward or p2 backward based on conditions until they meet or cross.

Build-Up - 7 Steps

1

Foundation

Understanding Array and Index Basics

Concept: Learn what arrays are and how to access elements using indexes.

An array is a list of items stored in order. Each item has a position called an index, starting from 0. You can get or change an item by using its index. For example, in Go: arr := []int{10, 20, 30}; arr[1] is 20.

Result

You can read or write any element in the array by its position.

Knowing how to access array elements by index is essential because two pointers rely on moving through these positions.

2

Foundation

Basic Looping Over Arrays

Concept: Learn how to move through an array using loops.

A loop lets you visit each element in order. For example, a for loop in Go: for i := 0; i < len(arr); i++ { // use arr[i] } This visits every element from start to end.

Result

You can process or check every element in the array one by one.

Understanding loops helps you see how two pointers can replace or improve this by moving from both ends.

3

Intermediate

Introducing Two Pointers Moving Inwards

🤔Before reading on: do you think two pointers starting at both ends should move towards each other or away to find pairs that sum to a target? Commit to your answer.

Concept: Use two pointers starting at the beginning and end of a sorted array to find pairs matching a condition.

Imagine a sorted array and a target sum. Place one pointer at the start (left) and one at the end (right). Add the two values: - If sum equals target, you found a pair. - If sum is less than target, move left pointer right to increase sum. - If sum is more than target, move right pointer left to decrease sum. Repeat until pointers cross.

Result

Pairs that add up to the target are found efficiently without checking all pairs.

Knowing how to move pointers based on conditions avoids unnecessary checks and speeds up the search.

4

Intermediate

Two Pointers for Partitioning Arrays

🤔Before reading on: do you think two pointers can help separate even and odd numbers in one pass? Commit to yes or no.

Concept: Use two pointers to rearrange an array by moving elements to correct sides in one pass.

Place one pointer at the start and one at the end. Move the start pointer forward until it finds an odd number. Move the end pointer backward until it finds an even number. Swap these two elements. Repeat until pointers meet. This partitions the array into evens on one side and odds on the other.

Result

Array is rearranged with all even numbers on one side and odd numbers on the other in one pass.

Two pointers can efficiently rearrange arrays without extra space or multiple passes.

5

Intermediate

Two Pointers for Removing Duplicates

🤔Before reading on: do you think two pointers can help remove duplicates from a sorted array in-place? Commit to yes or no.

Concept: Use one pointer to track the position of unique elements and another to scan through the array.

In a sorted array, duplicates are next to each other. Use a slow pointer to mark the position of the last unique element. Use a fast pointer to scan the array: - When fast finds a new unique element, move slow forward and copy the new element there. - Continue until the end. This keeps only unique elements at the start.

Result

Array start contains unique elements; duplicates are removed in-place.

Two pointers can solve in-place problems by separating scanning and writing positions.

6

Advanced

Two Pointers in Unsorted Arrays with Conditions

🤔Before reading on: can two pointers work efficiently on unsorted arrays without sorting first? Commit to yes or no.

Concept: Two pointers can be adapted for unsorted arrays but often require extra logic or sorting first.

For unsorted arrays, two pointers alone may not solve problems like pair sums efficiently. One approach is to sort the array first, then apply two pointers. Alternatively, use hash maps for direct lookups. Two pointers shine when the array is sorted or when scanning for subarrays with conditions like sums or lengths.

Result

Two pointers work best with sorted arrays or specific conditions; otherwise, other methods may be better.

Understanding the limits of two pointers helps choose the right tool for the problem.

7

Expert

Optimizing Two Pointer Algorithms in Go

🤔Before reading on: do you think using pointers to array elements in Go improves two pointer performance? Commit to yes or no.

Concept: Learn how Go's memory model and slices affect two pointer implementations and how to optimize them.

In Go, slices are references to arrays with length and capacity. Two pointers are usually indexes, not actual pointers. Using indexes avoids unsafe code and keeps clarity. For performance: - Avoid unnecessary slice copies. - Use simple index variables. - Minimize bounds checks by careful loop conditions. - Use in-place swaps to reduce memory. This keeps two pointer code fast and safe.

Result

Two pointer code in Go runs efficiently and safely with proper use of indexes and slices.

Knowing Go's slice internals helps write two pointer code that is both clear and performant.

Under the Hood

Two pointers work by maintaining two positions in the array and moving them based on comparisons or conditions. This reduces the number of checks from potentially n² to n by eliminating impossible pairs early. Internally, this uses simple index arithmetic and conditional jumps, which are very fast. In Go, slices provide a window into arrays, and indexes move within this window without copying data.

Why designed this way?

The technique was designed to optimize problems where checking all pairs is too slow. By leveraging sorted data or problem constraints, two pointers reduce complexity. Alternatives like nested loops were too slow, and hash-based methods use extra memory. Two pointers strike a balance between speed and memory use.

┌─────────────┐
│   Array     │
│ [a0, a1,...,an-1] │
└─────┬───────┘
      │
┌─────▼───────┐
│ Left Pointer│ -> moves right
└─────────────┘

┌─────────────┐
│Right Pointer│ -> moves left
└─────────────┘

Pointers move towards each other based on conditions until they meet or cross.

Myth Busters - 3 Common Misconceptions

Quick: Do two pointers always require the array to be sorted? Commit yes or no.

Common Belief: Two pointers only work if the array is sorted.

Reality: While two pointers are most efficient on sorted arrays, they can also be used on unsorted arrays for tasks like partitioning or removing duplicates with proper logic.

Why it matters: Believing sorting is always required limits the use of two pointers and misses simpler solutions for some problems.

Quick: Do two pointers always move towards each other? Commit yes or no.

Common Belief: Two pointers always start at opposite ends and move inward.

Reality: Two pointers can start anywhere and move in any direction depending on the problem, such as both moving forward at different speeds or one chasing the other.

Why it matters: Assuming fixed pointer movement patterns restricts problem-solving creativity and understanding.

Quick: Is two pointer technique always faster than hash-based methods? Commit yes or no.

Common Belief: Two pointers are always the fastest solution for pair or subarray problems.

Reality: Two pointers are fast for sorted arrays and certain problems, but hash-based methods can be faster or simpler for unsorted arrays or when order doesn't matter.

Why it matters: Overusing two pointers can lead to inefficient or complex code when simpler methods exist.

Expert Zone

1

Two pointers can be combined with binary search to solve complex problems like finding pairs with a given sum in O(n log n) time.

2

In Go, careful loop conditions prevent slice bounds checks inside two pointer loops, improving performance.

3

Two pointers can be adapted to work with linked lists or streams by simulating indexes with references or iterators.

When NOT to use

Avoid two pointers when the array is unsorted and the problem requires random access or when hash-based or sorting methods provide simpler or faster solutions. For example, use hash maps for pair sums in unsorted arrays or sliding window for variable-length subarrays.

Production Patterns

Two pointers are used in real systems for tasks like merging sorted logs, removing duplicates in data streams, partitioning data for parallel processing, and optimizing search queries on sorted datasets.

Connections

Sliding Window Technique

Builds on two pointers by fixing one pointer and moving the other to find subarrays with conditions.

Understanding two pointers helps grasp sliding windows, which are essential for efficient subarray problems.

Binary Search

Two pointers can be combined with binary search to optimize searching pairs or ranges in sorted arrays.

Knowing two pointers clarifies how binary search can narrow search space efficiently in combination.

Human Decision Making

Both involve narrowing options step-by-step by comparing and adjusting choices based on feedback.

Recognizing this connection helps appreciate how algorithms mimic natural problem-solving strategies.

Common Pitfalls

#1 Moving pointers incorrectly causing infinite loops or missed elements.

Wrong approach:

for left, right := 0, len(arr)-1; left < right; {
if arr[left]+arr[right] == target {
// found pair
} else if arr[left]+arr[right] < target {
right++ // wrong: moving right pointer forward
} else {
left-- // wrong: moving left pointer backward
}
}

Correct approach:

for left, right := 0, len(arr)-1; left < right; {
if arr[left]+arr[right] == target {
// found pair
} else if arr[left]+arr[right] < target {
left++ // move left pointer forward
} else {
right-- // move right pointer backward
}
}

Root cause:

Confusing which pointer to move based on sum comparison leads to pointers moving away from each other or out of bounds.

#2 Using two pointers on unsorted arrays without sorting or extra logic, expecting correct results.

Wrong approach:

left, right := 0, len(arr)-1
for left < right {
if arr[left]+arr[right] == target {
// found pair
}
left++
right--
}

Correct approach:

// Sort array first or use hash map for unsorted arrays
sort.Ints(arr)
left, right := 0, len(arr)-1
for left < right {
// two pointer logic
}

Root cause:

Assuming two pointers work on any array without considering order or problem constraints.

#3 Not updating pointers after finding a valid pair, causing infinite loops.

Wrong approach:

for left, right := 0, len(arr)-1; left < right; {
if arr[left]+arr[right] == target {
fmt.Println(arr[left], arr[right])
// forgot to move pointers
} else if arr[left]+arr[right] < target {
left++
} else {
right--
}
}

Correct approach:

for left, right := 0, len(arr)-1; left < right; {
if arr[left]+arr[right] == target {
fmt.Println(arr[left], arr[right])
left++
right--
} else if arr[left]+arr[right] < target {
left++
} else {
right--
}
}

Root cause:

Forgetting to move pointers after finding a pair causes the loop to repeat the same check endlessly.

Key Takeaways

The two pointer technique uses two markers moving through an array to solve problems efficiently by reducing unnecessary checks.

It works best on sorted arrays but can be adapted for other tasks like partitioning or removing duplicates.

Understanding how and when to move each pointer based on conditions is key to avoiding bugs and infinite loops.

In Go, using indexes with slices keeps two pointer code safe and performant without complex pointer arithmetic.

Knowing the limits and alternatives to two pointers helps choose the best approach for each problem.

Practice

1. What is the main idea behind the Two Pointer Technique when used on arrays?

easy

A. Use two arrays to store elements separately.

B. Use one pointer to traverse and another to store values.

C. Use two indices to scan the array from different ends or positions simultaneously.

D. Use two nested loops to compare all pairs of elements.

Solution

1. Step 1: Understand the technique

   The two pointer technique uses two indices or pointers to traverse the array, often starting from different ends or positions.

2. Step 2: Compare with other options

   The other options describe different methods, but only using two indices to scan the array from different ends or positions simultaneously correctly describes the two pointer approach.

3. Final Answer:

   Use two indices to scan the array from different ends or positions simultaneously. -> Option C

4. Quick Check:

   Two pointers move independently to solve problems efficiently [OK]

Hint: Two pointers move from ends or positions to reduce time [OK]

Common Mistakes:

• Thinking it uses two separate arrays
• Confusing with nested loops approach
• Assuming only one pointer moves

2. Which of the following is the correct way to initialize two pointers left and right for an array arr in Go?

easy

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

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

C. left := -1; right := len(arr)

D. left := 0; right := len(arr)

Solution

1. Step 1: Understand array indexing in Go

   Arrays and slices in Go are zero-indexed, so the first element is at index 0 and the last at len(arr)-1.

2. Step 2: Check pointer initialization

   Setting left to 0 and right to len(arr)-1 correctly points to the first and last elements respectively.

3. Final Answer:

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

4. Quick Check:

   Start pointers at 0 and last index [OK]

Hint: Start left at 0 and right at last index (len-1) [OK]

Common Mistakes:

• Setting right to len(arr) causes out-of-range error
• Starting left at 1 misses first element
• Using negative indices which Go does not support

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

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

medium

A. 0 4

B. 1 3

C. 2 3

D. No output

Solution

1. Step 1: Trace the pointers and sums

   Initial pointers: left=0 (arr[0]=1), right=4 (arr[4]=9), sum=10 ==10, so prints 0 4 and breaks.

2. Step 2: Verify the condition and loop

   Actually, sum=1+9=10, so it prints 0 4 and breaks immediately.

3. Final Answer:

   0 4 -> Option A

4. Quick Check:

   Sum 1+9=10 at indices 0 and 4 [OK]

Hint: Check sum at pointers; print indices when sum matches target [OK]

Common Mistakes:

• Not breaking after first match
• Confusing indices with values
• Incorrect pointer updates

4. Find the error in the following Go code using two pointers to find if any two numbers sum to 8:

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

medium

A. The loop condition should be left <= right

B. left pointer should start at 1

C. sum calculation is incorrect

D. right is initialized to len(arr), which is out of range

Solution

1. Step 1: Check pointer initialization

   right is set to len(arr), but valid indices go from 0 to len(arr)-1. This causes out-of-range error when accessing arr[right].

2. Step 2: Verify other parts

   left starting at 0 is correct, loop condition left < right is valid, sum calculation is correct.

3. Final Answer:

   right is initialized to len(arr), which is out of range -> Option D

4. Quick Check:

   Array indices go 0 to len-1, not len [OK]

Hint: Initialize right pointer to len(arr)-1 to avoid out-of-range [OK]

Common Mistakes:

• Setting right to len(arr) causes runtime error
• Changing loop condition unnecessarily
• Misunderstanding array indexing

5. Given a sorted array arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}, use the two pointer technique to find all pairs that sum to 10. Which of the following Go code snippets correctly prints all such pairs?

hard

A. left, right := 0, len(arr)-1
for left < right {
sum := arr[left] + arr[right]
if sum == 10 {
fmt.Println(arr[left], arr[right])
left++
right--
} else if sum < 10 {
left++
} else {
right--
}
}

B. left, right := 0, len(arr)-1
for left <= right {
sum := arr[left] + arr[right]
if sum == 10 {
fmt.Println(arr[left], arr[right])
left++
right--
} else if sum < 10 {
left++
} else {
right--
}
}

C. left, right := 0, len(arr)
for left < right {
sum := arr[left] + arr[right]
if sum == 10 {
fmt.Println(arr[left], arr[right])
left++
right--
} else if sum < 10 {
left++
} else {
right--
}
}

D. left, right := 1, len(arr)-1
for left < right {
sum := arr[left] + arr[right]
if sum == 10 {
fmt.Println(arr[left], arr[right])
left++
right--
} else if sum < 10 {
left++
} else {
right--
}
}

Solution

1. Step 1: Check pointer initialization and loop condition

   left, right := 0, len(arr)-1 for left < right { sum := arr[left] + arr[right] if sum == 10 { fmt.Println(arr[left], arr[right]) left++ right-- } else if sum < 10 { left++ } else { right-- } } initializes left=0 and right=len(arr)-1, which are valid indices. Loop runs while left < right to avoid duplicates and out-of-range.

2. Step 2: Verify pointer updates on sum match

   When sum == 10, both pointers move inward to find other pairs. This correctly finds all pairs without repeats.

3. Final Answer:

   left, right := 0, len(arr)-1 for left < right { sum := arr[left] + arr[right] if sum == 10 { fmt.Println(arr[left], arr[right]) left++ right-- } else if sum < 10 { left++ } else { right-- } } -> Option A

4. Quick Check:

   Two pointers move inward, printing pairs when sum matches [OK]

Hint: Move both pointers inward on match to find all pairs [OK]

Common Mistakes:

• Using right = len(arr) causes index error
• Loop condition left <= right prints duplicates
• Starting left at 1 misses pairs with first element