Two-pointer technique

2.1 Defining the Two-pointer technique.

The Two-pointer technique is a strategy used for solving various array and string problems, where you use two pointers (indices) that move across the data following specific rules. This method allows you to effectively solve problems related to finding pairs of elements, subsets that meet specific conditions.

This technique involves using two pointers that are usually initialized at opposite ends of the data structure and move toward each other or according to a specific rule. The two-pointer method can significantly reduce the time complexity of an algorithm compared to more naive approaches.

Main Principles

1. Initialization of two pointers: The pointers can be set at the beginning and end of an array or string, or at different indices depending on the task.
2. Moving pointers: Pointers move according to a specific rule (for example, both pointers move toward the center, or one pointer moves forward while the other stays).
3. Condition Check: At each step, a condition is checked that determines further movement of the pointers or the termination of the algorithm.

Time Complexity:

O(n) — in most cases, as both pointers pass through the array one or more times, but not more than O(n) iterations in total.

For some tasks, depending on the conditions and initial positions of the pointers, the time complexity might be O(n log n) or O(n^2), but that's rare.

Examples of problems solved using the two-pointer technique:

2.2 Finding two numbers in an array whose sum equals a given number.

Task:

Find two numbers in a sorted array that sum up to a given number target.

Solution:

Initialize one pointer at the start of the array, and the other at the end. Check the sum of the elements under the pointers:

• If the sum equals target, return the indices.
• If the sum is less than target, move the left pointer to the right.
• If the sum is more than target, move the right pointer to the left.

Time Complexity: O(n).

Example code in Python:

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None

2.3 Checking for a Palindrome

Task:

Check if a string is a palindrome.

Solution:

Initialize pointers at the start and end of the string. Compare the characters under the pointers:

• If the characters match, move both pointers toward each other.
• If the characters don't match, the string is not a palindrome.

Time Complexity: O(n).

Example code in Python:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

2.4 Removing duplicates from a sorted array

Task:

Remove duplicates from a sorted array.

Solution:

Use two pointers, one for the current position in the resulting array, and the other for iterating through all elements:

• If the current element is not equal to the previous one, write it to the resulting array.

Time Complexity: O(n).

Example code in Python:

def remove_duplicates(arr):
    if not arr:  # If the array is empty, return an empty array
        return []

    write_index = 1  # Pointer for writing unique values

    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:  # If the current element is not equal to the previous one
            arr[write_index] = arr[i]  # Write the unique element at the write_index position
            write_index += 1  # Move the pointer

    return arr[:write_index]  # Return the array with unique values, trimmed to write_index

# Example usage
arr = [1, 1, 2, 2, 2, 3, 4, 4, 5]
result = remove_duplicates(arr)
print(result)  # Expected result: [1, 2, 3, 4, 5]