Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 6

Two-Pointer Technique for Arrays and Strings

Recommended resources

Introduction

Welcome to the next step in our journey to master data structures and algorithms. In the last lesson, you gained proficiency with std::vector and std::string, the essential C++ tools for handling sequential data. Now, we will learn how to operate on this data with remarkable efficiency.

This lesson introduces the two-pointer technique, a classic algorithmic pattern that is simple in concept but powerful in application. You will learn how to use two indices to traverse an array or string, drastically reducing the time complexity of your solutions—often from a quadratic O(N^2) to a linear O(N). Mastering this technique is crucial for coding interviews, as it demonstrates your ability to move beyond brute-force thinking and devise optimized algorithms. We will start with the fundamental pattern and then explore its application in several common interview problems.

The Core Idea: From Brute-Force to Optimal

Many problems involving arrays or strings ask you to find a pair of elements that satisfy a certain condition. The most straightforward approach is often to use nested loops: one loop to pick the first element, and a second loop to check it against every other element. This results in an O(N^2) time complexity. While correct, this is often too slow for interview constraints.

The two-pointer technique offers a much faster alternative, typically by processing the array in a single pass. The most common variant of this technique works on a sorted array, with one pointer starting at the beginning and the other at the end. The pointers then move towards each other based on a specific condition.

Let's explore this with a classic problem: find if a pair of numbers in a sorted array sums up to a given target.

Two Pointers Technique - GeeksforGeeks

This article from GeeksforGeeks introduces the two-pointer technique using the "Sum of Pair Equal to Target" problem. It's a great starting point to see the contrast between a naive approach and an optimized one.

First, read the example problem to understand the goal. Then, review the Naive Method and its accompanying C++ code. This section formalizes the O(N^2) brute-force solution we just discussed.

Now, let's see how we can optimize this. By using two pointers, one at each end of the sorted array, we can make an intelligent decision at each step.

An illustration of the two-pointer technique. For a target of 8, the pointers start at 2 and 18. Their sum, 20, is greater than the target, so the right pointer is moved inwards to find a smaller sum.

The logic is as follows:

  1. Initialize a left pointer to the first element (index 0) and a right pointer to the last element (index n-1).
  2. While left is less than right:
    • Calculate sum = array[left] + array[right].
    • If sum == target, you've found the pair.
    • If sum < target, the sum is too small. To increase it, you must move the left pointer to the right (left++), as this brings in a larger number.
    • If sum > target, the sum is too large. To decrease it, you must move the right pointer to the left (right--), as this brings in a smaller number.
  3. If the loop finishes without finding a pair, no such pair exists.

This approach elegantly eliminates pairs from consideration at each step, allowing us to find a solution in a single pass. The following video provides an excellent walkthrough of this exact logic.

Two pointers | Brute force and Optimised Solution discussed

This video from RisingBrain contrasts the brute-force and two-pointer solutions for the "Two Sum II" problem (which is identical to our example). Pay close attention to the reasoning for moving the left or right pointer.

Watch the segment from the introduction of the optimized approach to the end of the complexity analysis. The presenter clearly explains how the sorted nature of the array allows for this efficient strategy. Then, if you'd like to see the C++ code implemented, you can watch the coding part.

To solidify your understanding, let's look at the formal proof of why this method is correct and review the C++ implementation.

Two Pointers Technique - GeeksforGeeks

We'll return to the GeeksforGeeks article to see the implementation and justification for the two-pointer approach.

Read the section on the Two-Pointer Technique, including the C++ code. Then, carefully read the proof in the section How does this work?. This part is crucial, as it explains why you can safely discard elements without missing a potential solution.

Applications of the Two-Pointer Technique

The power of this technique lies in its adaptability. The core idea of traversing from two ends can be applied to a variety of problems beyond simply finding a sum. As you prepare for coding interviews, you'll find that recognizing a problem as a candidate for the two-pointer technique is a valuable skill.

The following resource presents several classic interview problems that can be solved efficiently using this pattern.

Two Pointers in C++: A Path to Optimized Algorithms

This Medium article showcases several LeetCode problems and their solutions using the two-pointer technique. We will focus on three distinct examples to see the versatility of the pattern.

Valid Palindrome: Start by reading the Valid Palindrome section. This is a great example of applying the technique to a std::string, where pointers check for character equality while moving inwards. Notice how the pointers also handle skipping non-alphanumeric characters. Container With Most Water: Next, read the Container With Most Water section. This problem requires a clever insight. The area is limited by the shorter of the two lines. To find a potentially larger area, you must move the pointer corresponding to the shorter line. This is a fantastic example of adapting the pointer-movement logic to a different kind of optimization problem. 3Sum: Finally, read the 3Sum section. This is a common and more advanced interview question. The solution cleverly reduces the problem: it sorts the array, then iterates through it with a single loop. For each element nums[i], it uses the two-pointer technique on the rest of the array to find two numbers that sum up to -nums[i]. This demonstrates how two-pointers can be a building block within a more complex algorithm.

These examples demonstrate that the two-pointer technique isn't a rigid formula but a flexible pattern. The key is to first sort the data (if it isn't already), and then define the logic for moving the left and right pointers based on the specific condition you need to satisfy.

Conclusion

In this lesson, we dissected the two-pointer technique, transforming a common O(N^2) brute-force problem into an elegant O(N) solution. This is a prime example of the algorithmic thinking that is highly valued in technical interviews. You've not only learned the fundamental pattern but also seen its application across different types of array and string problems.

Key Takeaways:

  • Core Principle: The two-pointer technique uses two indices to traverse a data structure, often from opposite ends, to solve problems in a single pass.
  • Prerequisite: The most common pattern, where pointers move towards each other, typically requires the array or sequence to be sorted.
  • Time & Space Complexity: It usually reduces time complexity from O(N^2) to O(N) (or O(N log N) if sorting is needed first) and uses O(1) auxiliary space, making it highly efficient.
  • Versatility: The logic for moving the pointers is problem-specific. We saw this in finding a target sum, checking for a palindrome, maximizing an area, and as a subroutine in the 3Sum problem.

In our next lesson, we will explore a closely related pattern: the sliding window technique. While it also uses two pointers, they typically move in the same direction to analyze contiguous subarrays or substrings, opening up a new category of problems for us to solve efficiently.