Beyond Two Pointers

A Complete Guide to Index-Based Problem Solving

Beyond Two Pointers

The term “two pointers” gets mentioned often, but it’s really not a single, one-size-fits-all method. Think of it as a flexible strategy — sometimes you only need one pointer, other times three or more. In this guide, we’ll explore how pointers of all kinds can tackle different challenges, showing that “two pointers” is just the beginning.

I recommend you to follow this guide with embedded practice problems on the new Faangshui platform here.

---

What is a Pointer?

In C, a pointer is a variable that holds the memory address of another variable. For example:

int array[3] = {1, 2, 3};
int *pointer = &array[0];
printf("First element is %d\n", *pointer); // prints 1

*pointer = 10;  // change the first element
printf("Now first element is %d\n", array[0]); // prints 10

pointer++; // move pointer to the next element
printf("Second element is %d\n", *pointer); // prints 2

Because we have the address of an element in an array, we can directly access or modify its value, or shift the pointer itself (pointer arithmetic). This flexibility is what makes pointers powerful.

Index Pointers in High-Level Languages

In higher-level languages like Python or JavaScript, we don’t typically manipulate raw memory addresses. Instead, we store an index that effectively points to an element in an array. Think of RAM as an array of bytes — tracking an index is like using a “pointer” into that array. You can read, modify, or move to other elements by changing the index.

To distinguish from low-level memory address pointers, we’ll call these index pointers. Although pointers can apply to linked lists as well, this guide focuses on index pointers in arrays.

---

Single Pointer

You’ve likely already used a single pointer without realizing it. A basic example is finding the index of the maximum value in an array:

max_pointer = 0
for i in range(len(nums)):
    if nums[i] > nums[max_pointer]:
        max_pointer = i
print(f"The index of the maximum value is {max_pointer}")

Here, max_pointer stores the index of the currently most interesting element—in this case, the largest value so far. As the loop progresses, this pointer updates whenever a new maximum is found.

Practice Task
Practice using single pointers here.

---

Pointers Over Multiple Arrays

Sometimes you’ll need to work with multiple arrays where standard linear traversal isn’t possible because you can’t simply iterate from the beginning to the end of one array. In these cases, you can use multiple single pointers — one for each array.

Example: Merging Two Sorted Arrays
Task: given two sorted arrays, merge them into a single sorted array.

nums1 = [1, 2, 3]
nums2 = [2, 5, 6]
merged_array = [1, 2, 2, 3, 5, 6]

Since you can’t just iterate linearly from start to finish in either array (you don’t know which element is next in sorted order), index pointers are ideal.

Defining the Pointers

• pointer1: Tracks the current position in nums1 — the next element not yet added to merged_array.

• pointer2: Tracks the current position in nums2 — the next element not yet added to merged_array. Initially, both pointers start at index 0 of their respective arrays.

Merging Process

• Compare nums1[pointer1] and nums2[pointer2].

• Whichever element is smaller goes into merged_array, and the corresponding pointer is incremented.

• Repeat until one pointer reaches the end of its array.

• Append any remaining elements from the other array.

pointer1 = 0
pointer2 = 0
merged_array = []

while pointer1 < len(nums1) and pointer2 < len(nums2):
    if nums1[pointer1] < nums2[pointer2]:
        merged_array.append(nums1[pointer1])
        pointer1 += 1
    else:
        merged_array.append(nums2[pointer2])
        pointer2 += 1

# Append remaining elements from nums1 or nums2.
while pointer1 < len(nums1):
    merged_array.append(nums1[pointer1])
    pointer1 += 1

while pointer2 < len(nums2):
    merged_array.append(nums2[pointer2])
    pointer2 += 1

Notice that pointer1 and pointer2 move independently. Each pointer is responsible for tracking progress in its own array.

Practice Task
Practice using pointers over multiple arrays in the task linked here.

---

Fast and Slow Pointers

Fast and slow pointers are a clever technique for working with arrays or linked structures. They move at different speeds to tackle a range of problems—everything from detecting cycles to in-place array modifications.

Example: Removing Duplicates in a Sorted Array
Task: remove duplicates while keeping all unique elements at the beginning.

slow = 0
for fast in range(1, len(nums)):
    if nums[fast] != nums[slow]:
        slow += 1
        nums[slow] = nums[fast]

How It Works

• Fast pointer: Scans through every element in the array.

• Slow pointer: Keeps track of where the next unique element should be placed.

• Writing unique values: Each time nums[fast] is different from nums[slow], move slow forward and store nums[fast] there.

By the time you finish iterating:

• All unique elements are compacted at the front of the array.

• slow indicates the index of the last unique element.

This approach processes the array in a single pass (O(n) time), making it highly efficient for sorting and deduplication tasks.

Practice Task
Practice using fast and slow pointers in the task linked here.

---

Converging Pointers

The converging pointers technique places two pointers at opposite ends of an array and moves them toward each other based on specific conditions. It’s commonly used for problems involving comparisons, finding pairs, or narrowing search spaces in a sorted array.

Example: Two-Sum in a Sorted Array
Task: given a sorted array and a target sum, find two numbers that add up to the target.

left = 0
right = len(nums) - 1

while left < right:
    sum = nums[left] + nums[right]
    if sum == target
        return [left, right]
    elif sum < target
        left += 1
    else
        right -= 1

How it works:

1. Initialize pointers: set left at the start and right at the end of the array.

2. Evaluate and adjust:

   • If nums[left] + nums[right] equals the target, the solution is found.

   • If the sum is too small, move left rightward to increase it.

   • If the sum is too large, move right leftward to decrease it.

3. Stop condition: continue until the pointers meet or you’ve found a valid pair.

Because the array is sorted, every pointer adjustment precisely eliminates a chunk of the search space. Each element is examined at most once, resulting in an efficient O(n) solution.

Practice Task
Practice using converging pointers in the task linked here.

---

Role-Based Pointers

Role-Based Pointers is a technique where each pointer has a specific task or role, allowing you to address different parts of a problem at the same time. Unlike other pointer techniques where pointers often depend on one another, in this approach each pointer operates independently based on its assigned role.

Example: Rearranging Even/Odd Elements by Index
Task: rearrange an array so that even indices hold even numbers and odd indices hold odd numbers. Assume the array has an equal number of even and odd elements.

nums = [3, 1, 2, 4]
result = [2, 3, 4, 1]

Solution Using Role-Based Pointers
Let's define two pointers:

• even_idx: Tracks the next even index where an even number should go.

• odd_idx: Tracks the next odd index where an odd number should go.

Here is how the code looks:

even_idx = 0
odd_idx = 1

while even_idx < len(nums) and odd_idx < len(nums):
    if nums[even_idx] % 2 == 0:
        even_idx += 2  # Even number is in the correct position
    elif nums[odd_idx] % 2 == 1:
        odd_idx += 2  # Odd number is in the correct position
    else:
        swap(nums[even_idx], nums[odd_idx])

Each pointer has a specific role:

• even_idx: Ensures even numbers are at even indices, moving forward only when the condition is met.

• odd_idx: Ensures odd numbers are at odd indices, moving forward only when the condition is met. If each pointer finds a number at the wrong index, a swap corrects both simultaneously.

By assigning each pointer its own job, this problem becomes a series of straightforward checks and swaps rather than a single pointer juggling multiple conditions.

Practice Task
Practice using role-based pointers in the task linked here.

---

Binary Search

Yes, you read that right — binary search can be seen as an index pointers problem. It’s an algorithm that uses pointers (indexes) to locate a target value in a sorted array efficiently. These pointers mark the boundaries of the search space, and at each step, you check the midpoint to decide which half of the array to explore next.

Intuition behind binary search
Imagine searching for a specific page in a book:

• Open roughly in the middle.

• Check if the target page is earlier or later than where you opened.

• Move left or right, halving the search area until you find the page. Binary search applies this same strategy to an array, repeatedly dividing the problem space in half.

Example: Finding an Element in a Sorted Array
Task: find the index of 7 in the sorted array nums = [2, 4, 7, 10, 14, 15, 17, 29, 45].

1. Start with two pointers:

   • low = 0 (the first index).

   • high = len(nums) - 1 = 8 (the last index).

2. Calculate the midpoint:

   • mid = (low + high) // 2 = (0 + 8) // 2 = 4.

3. Check if nums[mid] is the target:

   • nums[4] = 14, which is not the target.

4. Narrow down the search space:

   • Since 7 is less than 14, we know it must be in the left half.

   • Update high = mid - 1 = 4 - 1 = 3.

5. Calculate the new midpoint:

   • mid = (low + high) // 2 = (0 + 3) // 2 = 1.

6. Check if nums[mid] is the target:

   • nums[1] = 4, which is not the target.

7. Narrow down the search space:

   • Since 7 is greater than 4, we know it must be in the right half.

   • Update low = mid + 1 = 1 + 1 = 2.

8. Calculate the new midpoint:

   • mid = (low + high) // 2 = (2 + 3) // 2 = 2.

9. Check if nums[mid] is the target:

   • nums[2] = 7, which is the target.

10. Return the index of the target:

    • The index of 7 is 2.

This is a simple example, but binary search can handle much larger arrays and more complex search conditions. Putting it into code, you get:

low = 0
high = len(nums) - 1

while low <= high:
    mid = (low + high) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

return -1  # Target not found

Variations of Binary Search
Many versions of binary search exist, such as:

• Lower bound / upper bound: find the first or last position of a value.

• Search insert position: identify where a target should be inserted if not present.

• Rotated array search: adaptations for arrays rotated around a pivot.

Binary search’s power lies in its logarithmic time complexity, making it efficient for large datasets. Give it a try in the practice task linked here to sharpen your skills.

---

Two Pointers Summary

Throughout this guide, we explored how index pointers can efficiently solve an array of problems by focusing on specific positions, traversing arrays in custom orders, or using multiple pointers to handle different tasks. Here are the key takeaways:

1. Indices Are Just Numbers
Think of indices as ordinary integers stored in variables. You can add, subtract, or otherwise manipulate them. When you use these index variables to navigate an array, they effectively act as pointers.

2. Track Important Positions
In many problems, certain positions in an array matter more than others. By assigning pointers to track these positions, you can isolate, modify, or compare them as needed, all within a single pass or minimal passes over the data.

3. Custom Traversals
You’re not restricted to a simple for-loop from start to finish. Index pointers let you move through the array in any order, skipping or revisiting elements based on problem-specific logic.

4. Beyond Arrays
While we focused on arrays, the same pointer logic can apply to linked lists, strings, or even trees. Anywhere you deal with references or indices, pointer-based approaches can shine.

5. Sorted Order is a Hint
Though not mandatory, a sorted array often suggests that pointers can solve the problem. Even if an array isn’t sorted initially, you can sort it first and then apply two-pointer methods for more efficient solutions.

---

By keeping these principles in mind, you’ll be able to recognize where pointers can simplify your solutions and optimize your algorithms, whether you’re dealing with arrays, lists, or other data structures.

Check out the practice tasks on index pointers to sharpen your skills: Index Pointers / Two Pointers Practice Problems

Happy coding,

Nurbo