Dancing with Data: Mastering the Two-Pointer Technique for Efficient Algorithms

What is the Two Pointers Technique?

The Two Pointers technique involves using two pointers that either:

1. Move towards each other
2. Move in the same direction at different speeds

These pointers help us efficiently solve problems that might otherwise require nested loops, thus reducing time complexity from O(n²) to O(n) in many cases.

Common Scenarios for Two Pointers

1. Searching pairs in a sorted array
2. Reversing an array or string
3. Removing duplicates
4. Palindrome checking
5. Merging two sorted arrays

Let’s explore a couple of these scenarios in detail.

Example 1: Two Sum II - Input Array is Sorted

Problem Statement:

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. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

• Input: numbers = [2,7,11,15], target = 9
• Output: [1,2]
• Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

• Input: numbers = [2,3,4], target = 6
• Output: [1,3]
• Explanation: The sum of 2 and 4 is 6. Therefore, index1 = 1, index2 = 3. We return [1, 3].

Example 3:

• Input: numbers = [-1,0], target = -1
• Output: [1,2]
• Explanation: The sum of -1 and 0 is -1. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Now, let’s look at the solution using the Two Pointers technique:

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed array
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

In this example, we use two pointers starting from opposite ends of the array. We move the pointers based on whether the current sum is less than or greater than the target.

Example 2: Remove Duplicates from Sorted Array

Problem Statement:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Example 1:

• Input: nums = [1,1,2]
• Output: 2, nums = [1,2,_]
• Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

• Input: nums = [0,0,1,1,1,2,2,3,3,4]
• Output: 5, nums = [0,1,2,3,4,,,,,_]
• Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).

Now, let’s look at the solution using the Two Pointers technique:

def removeDuplicates(nums):
    if not nums:
        return 0
    
    # Initialize the pointer for unique elements
    unique_pointer = 0
    
    # Iterate through the array
    for i in range(1, len(nums)):
        # If current element is different from the previous unique element
        if nums[i] != nums[unique_pointer]:
            # Move unique_pointer forward and update the element
            unique_pointer += 1
            nums[unique_pointer] = nums[i]
    
    # Return the length of the array with duplicates removed
    return unique_pointer + 1`

In this example, we use two pointers moving in the same direction, but at different speeds. The unique_pointer keeps track of the position where we should place the next unique element.

Diagram

Benefits of the Two Pointers Technique

1. Efficiency: Often reduces time complexity from O(n²) to O(n).
2. Space Optimization: Usually requires O(1) extra space.
3. Simplicity: Once mastered, it provides clean and intuitive solutions.

When to Use Two Pointers

Consider using the Two Pointers technique when:

• Dealing with sorted arrays
• Searching for pairs with a specific sum
• Reversing a string or array
• Removing duplicates
• Checking palindromes
• Merging two sorted arrays

Conclusion

The Two Pointers technique is a valuable tool in any programmer’s toolkit. It offers elegant solutions to a wide range of problems, especially those involving arrays and strings. By mastering this technique, you’ll be able to solve complex problems more efficiently and write cleaner, more optimized code.

Remember, practice is key to mastering any programming technique. Try solving various problems using the Two Pointers approach to reinforce your understanding and improve your problem-solving skills.