Two-Pointer Technique for Sorted Arrays

The Core Logic: Why Sorted Arrays are Key

The convergent two-pointer technique is most effective on sorted arrays. The sorted property is not just a hint; it's the enabling constraint that allows the algorithm to work intelligently.

Imagine you have two pointers, left at the start of a sorted array and right at the end. You are looking for a pair of numbers that satisfy a certain condition, often related to their sum.

The logic is simple yet powerful:

• If the sum of the elements at nums[left] and nums[right] is too small, you need a larger sum. Since the array is sorted, the only way to guarantee a potential increase is by moving the left pointer to the right (left++).
• If the sum is too large, you need a smaller sum. The only way to guarantee a potential decrease is by moving the right pointer to the left (right--).

This directional logic ensures that you never have to re-check a pair. With each step, you eliminate one of the elements from consideration, methodically narrowing the search space. This linear scan is what gives the algorithm its $O(n)$ time complexity.

Let's put this into practice with a classic problem.

Problem 1: Two Sum II - Input Array Is Sorted (LeetCode 167)

This problem is the quintessential example of the convergent two-pointer pattern.

1. Clarify

• Problem: Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.
• Input: A sorted array of integers (numbers) and a target integer (target).
• Output: An array containing the 1-based indices of the two numbers.
• Constraints: There is exactly one solution. You may not use the same element twice. The array is 1-indexed for the output, but 0-indexed for processing in Python.

2. Plan

• Brute-Force: The most straightforward approach is to use nested loops. The outer loop picks an element, and the inner loop checks every other element to see if their sum equals the target. This would work, but what's its complexity? It involves checking nearly every pair, resulting in an $O(n^2)$ time complexity. In an interview setting, this is the baseline you're expected to improve upon.

• Optimized Plan (Two Pointers): Since the input array is sorted, we can use the two-pointer technique.

  1. Initialize a left pointer to the start of the array (index 0).
  2. Initialize a right pointer to the end of the array (index len(numbers) - 1).
  3. Loop as long as left < right.
  4. Calculate current_sum = numbers[left] + numbers[right].
  5. If current_sum == target, we've found our pair. Return [left + 1, right + 1].
  6. If current_sum < target, the sum is too small. We need to increase it, so we move the left pointer: left += 1.
  7. If current_sum > target, the sum is too large. We need to decrease it, so we move the right pointer: right -= 1.

This approach guarantees we find the solution in a single pass. The time complexity will be $O(n)$ and the space complexity will be $O(1)$, as we only use a few variables for the pointers.

3. Implement

The following video from NeetCode provides an excellent walkthrough, starting with the brute-force idea and smoothly transitioning to the optimal two-pointer solution and its implementation.

As you saw in the video and in the "Two Pointers & Sliding Window" article from our last lesson, the code for this is remarkably concise.

def twoSum(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:



            # Found the solution, return 1-based indices
            return [left + 1, right + 1]
        elif current_sum < target:



            # Sum is too small, need a larger value
            left += 1
        else: # current_sum > target



            # Sum is too large, need a smaller value
            right -= 1

4. Verify

Let's trace the example numbers = [2, 7, 11, 15] and target = 9.

1. left = 0 (value 2), right = 3 (value 15). current_sum = 2 + 15 = 17.
2. 17 > 9, so the sum is too large. We decrement right to 2.
3. left = 0 (value 2), right = 2 (value 11). current_sum = 2 + 11 = 13.
4. 13 > 9, so the sum is too large. We decrement right to 1.
5. left = 0 (value 2), right = 1 (value 7). current_sum = 2 + 7 = 9.
6. 9 == 9, we found the solution. Return [left + 1, right + 1], which is [1, 2].

The logic holds. The loop correctly terminates and finds the single guaranteed solution.

Problem 2: Squares of a Sorted Array (LeetCode 977)

Now let's try a problem where the application of two pointers is slightly less direct but equally effective.

1. Clarify

• Problem: Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
• Input: A sorted array of integers (nums), which can contain negative numbers, positives, and zero.
• Output: A new array containing the squares of the input numbers, also sorted.
• Example: nums = [-4, -1, 0, 3, 10] -> output = [0, 1, 9, 16, 100].

Notice that simply squaring each element ([16, 1, 0, 9, 100]) does not produce a sorted array.

2. Plan

• Naive Approach: The most obvious solution is to first create a new array by squaring every number in nums. Then, sort this new array. The time complexity would be $O(n)$ for squaring and $O(n\log n)$ for sorting, making the total time complexity $O(n\log n)$. The space complexity is $O(n)$ to store the new array. Can we do better? Yes, by avoiding the expensive sort operation.

• Optimized Plan (Two Pointers):
  The key insight is that after squaring, the largest values will come from the numbers with the largest absolute values. In a sorted array, these are always at the extremes: the far left (most negative) and the far right (most positive).

  1. Initialize a left pointer at index 0 and a right pointer at index len(nums) - 1.
  2. Create a result array of the same size, filled with zeros (or any placeholder).
  3. We will populate the result array from right to left (i.e., from largest to smallest). Use a third pointer, i, initialized to the end of the result array.
  4. Loop as long as left <= right.
  5. Compare the absolute values of the numbers at the pointers: abs(nums[left]) and abs(nums[right]).
  6. If abs(nums[left]) > abs(nums[right]), the square of nums[left] is larger. Place it at result[i] and increment left.
  7. Otherwise, the square of nums[right] is larger or equal. Place it at result[i] and decrement right.
  8. In either case, decrement i to move to the next position in the result array.

This approach builds the sorted result array directly in a single pass. The time complexity is $O(n)$, and the space complexity is $O(n)$ for the required output array. This is more efficient than the $O(n\log n)$ naive approach.

3. Implement

This NeetCode video clearly explains this exact strategy.

Here is a Python implementation reflecting that logic:

def sortedSquares(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [0] * n  # Create a result array of the same size
    left, right = 0, n - 1
    



    # Iterate from the end of the result array to the beginning
    for i in range(n - 1, -1, -1):
        left_square = nums[left] * nums[left]
        right_square = nums[right] * nums[right]
        
        if left_square > right_square:
            result[i] = left_square
            left += 1
        else:
            result[i] = right_square
            right -= 1
            
    return result

4. Verify

Let's trace nums = [-4, -1, 0, 3, 10].

1. left=0 (-4), right=4 (10), i=4. left_square=16, right_square=100.
   • 100 > 16. result becomes [0,0,0,0,100]. right becomes 3. i becomes 3.
2. left=0 (-4), right=3 (3), i=3. left_square=16, right_square=9.
   • 16 > 9. result becomes [0,0,0,16,100]. left becomes 1. i becomes 2.
3. left=1 (-1), right=3 (3), i=2. left_square=1, right_square=9.
   • 9 > 1. result becomes [0,0,9,16,100]. right becomes 2. i becomes 1.
4. left=1 (-1), right=2 (0), i=1. left_square=1, right_square=0.
   • 1 > 0. result becomes [0,1,9,16,100]. left becomes 2. i becomes 0.
5. left=2 (0), right=2 (0), i=0. left_square=0, right_square=0.
   • 0 == 0. The else block runs. result becomes [0,1,9,16,100]. right becomes 1. i becomes -1.
6. The loop finishes. We return [0, 1, 9, 16, 100]. Correct.

Conclusion

In this lesson, we moved from the theory of the two-pointer pattern to its practical application in solving interview problems. You've seen how to deconstruct a problem, devise an optimal plan using this pattern, and implement a clean, efficient solution.

Key Takeaways:

• The convergent two-pointer pattern is a go-to technique for problems involving sorted arrays where you need to find pairs or relationships between elements.
• The core logic relies on moving pointers from the extremes inward, using the sorted property to make intelligent decisions about which pointer to move next.
• This pattern consistently reduces time complexity from a brute-force $O(n^2)$ to an optimal $O(n)$.
• The pattern is versatile. It can be used for searching (like "Two Sum II") and for constructing new sorted arrays (like "Squares of a Sorted Array").

Remember, when you encounter a problem with a sorted array, always ask yourself: "Can I use two pointers starting from the ends?"

In our next lesson, we will explore the Sliding Window technique. While it also uses two pointers, they typically move in the same direction to manage a "window" over a contiguous portion of an array, making it ideal for a different class of problems like finding the best subarray or substring.