Two Pointers: Sorted Arrays & Linked Lists

Hello! In our last session, we mastered the Sliding Window pattern, which is perfect for problems involving contiguous subarrays or substrings. Now, we'll explore another fundamental algorithmic tool: the Two Pointers technique.

While it also involves two pointers, its application is broader. Instead of defining a contiguous window, these pointers are used to track and compare individual elements, often allowing you to process a data structure in a single pass and with minimal extra space. By the end of this lesson, you will be able to solve common interview challenges on sorted arrays and linked lists using this versatile pattern.

1. The Two Pointers Technique: Core Concepts

The Two Pointers pattern is not a single algorithm but an umbrella term for several strategies that use two pointers to iterate through a data structure. This approach is highly effective for problems where you need to find a pair of elements that satisfy a certain condition or to process two parts of a data structure simultaneously. The efficiency gain comes from avoiding nested loops, typically reducing a potential $O(N^2)$ solution to an optimal $O(N)$ one.

There are two primary variations:

1. Opposite-Direction Pointers: One pointer starts at the beginning and the other at the end of the data structure. They move towards each other.
2. Same-Direction Pointers: Both pointers start at or near the beginning but move through the structure at the same or different speeds.

Let's explore these in the context of sorted arrays and linked lists.

2. Pointers from Opposite Ends: The Sorted Array Sweet Spot

When you encounter a problem with a sorted array, the opposite-direction pointer strategy should immediately come to mind. The sorted nature of the array provides a crucial property: moving the left pointer to the right increases the value, and moving the right pointer to the left decreases the value. This allows you to make intelligent decisions about which pointer to move.

Let's begin with an overview of this approach.

Example 1: Pair with Target Sum (A Classic Interview Question)

Consider the problem: "Given a sorted array of numbers and a target sum, find a pair in the array whose sum is equal to the given target."

A brute-force solution would be to check every possible pair, an $O(N^2)$ approach. With two pointers, we can do it in $O(N)$. Here’s how:

1. Place a pointer left at the first element and a pointer right at the last element.
2. Calculate the sum: current_sum = array[left] + array[right].
3. If current_sum equals the target, we've found our pair.
4. If current_sum is less than the target, we need a larger sum. Since the array is sorted, we can achieve this by moving the left pointer one step to the right.
5. If current_sum is greater than the target, we need a smaller sum. We achieve this by moving the right pointer one step to the left.
6. Repeat this process until the pointers cross each other.

The following image visualizes this process perfectly.

For a more detailed explanation and code example, the same article provides an excellent walkthrough.

This pattern is a powerful way to search for pairs in sorted arrays, and it extends to problems like "3Sum" where you can fix one element and apply the two-pointer approach to the rest of the array.

3. Pointers in the Same Direction

In this variation, the pointers typically move in the same direction but serve different roles. One might be a "fast" runner and the other "slow," or one could be a "read" pointer while the other is a "write" pointer.

Example 2: Removing Duplicates from a Sorted Array

Problem: "Given a sorted array, remove the duplicates in-place such that each element appears only once and return the new length of the array."

Here, we can use two pointers, let's call them nextNonDuplicate and i.

1. The nextNonDuplicate pointer starts at index 1 (since the first element is always unique to begin with) and marks the position where the next unique element should be placed.
2. The i pointer iterates through the array starting from index 1.
3. At each step, we compare array[i] with array[i-1]. If they are different, it means we've found a new unique element. We then copy array[i] to array[nextNonDuplicate] and advance nextNonDuplicate.
4. The i pointer always moves forward.

The result is that all unique elements are consolidated at the beginning of the array, and nextNonDuplicate gives us the length of this unique subarray.

Application to Linked Lists

The Two Pointers pattern is not limited to arrays. It's especially powerful for linked lists, where you don't have direct index access. Since you're already familiar with Go, you can think of pointers as references to ListNode structs, and movement happens via the Next field.

Two common linked list sub-patterns are:

• A fixed gap between pointers: Useful for finding elements relative to the end of the list.
• A fast and a slow pointer: Useful for finding the middle of a list or detecting cycles.

Let's explore these through a comprehensive resource.

As you can see, the fast/slow pointer approach elegantly solves the problem of finding the middle of a list in a single pass. This very same technique is the key to solving one of the most famous interview problems: cycle detection in a linked list.

4. How to Spot a Two-Pointer Problem

In a high-pressure interview setting, recognizing the right pattern is half the battle. So, when should you think "Two Pointers"?

To summarize the key signals from the video:

• Sorted Data: If you're given a sorted array (or you can sort it) and need to find a pair, triplet, or subsequence that meets a condition, the opposite-direction pattern is a strong candidate.
• Target Sum/Value: Problems that ask for a pair of values that sum up to a target.
• In-place Operations: Problems requiring you to modify an array or list in-place, like removing duplicates or partitioning elements.
• Comparing from Both Ends: Problems involving palindromes or other symmetric properties.
• Avoiding Nested Loops: If your brute-force solution involves a nested loop to compare pairs of elements, consider if a two-pointer approach could linearize it.
• Linked List Problems: Questions about finding the middle node, the k-th from the end, or detecting cycles are almost always solved with two pointers.

Conclusion

In this lesson, we've explored the Two Pointers technique, a versatile and efficient pattern for solving problems on linear data structures.

Key Takeaways:

• Core Principle: Use two pointers to traverse a data structure, often in a single pass, to reduce time complexity from quadratic to linear.
• Opposite-Direction Pointers: Ideal for sorted arrays when searching for pairs that satisfy a condition. The pointers move inward, narrowing the search space.
• Same-Direction Pointers: Can be used with a "fast/slow" or "read/write" dynamic. This is common for in-place array modifications and many linked list problems.
• Linked List Mastery: For linked lists, the "fixed gap" and "fast/slow" pointer variations are essential tools for finding nodes and identifying structural properties.

The "Fast and Slow Pointer" approach is particularly powerful. In our next lesson, we will dedicate our entire session to it, exploring how this sub-pattern, also known as the Tortoise and Hare algorithm, provides an elegant solution to the classic problem of detecting cycles in a linked list.