Dissecting the two pointer technique

Introduction.

Even after mastering the basics of arrays and lists, solving problems related to these data structures can sometimes feel overwhelming. Beyond understanding the data structures themselves - along with their operations and time and space complexities; grasping various techniques that apply to these problems can make the process much easier.
This is especially true given the wide variety of problems that can arise with arrays or lists. In this blog post, I'll focus on one such technique: the two-pointer technique, which is particularly effective for tackling array or list problems.

Two pointers.

The two pointer technique is an algorithmic approach, particularly effective for solving arrays or sequences. This means that the approach can also be applied to strings and linked lists.
It involves use of two distinct pointers to traverse the data structure, often leading to efficient solution with lower time complexity.

Types of two pointers.

Pointers moving towards each other.

This approach involves two pointers starting from opposite ends of the data structure and moving toward each other, meaning the pointers move in opposite directions. This type of two-pointer technique is particularly useful in scenarios where you want to find a pair of elements that meet certain conditions or when comparing elements from both ends. Common use cases include checking for a palindrome or finding pairs with a specific sum

Approach

1. Initialize the Pointers: Start with one pointer at the beginning (left) and the other at the end (right) of the data structure.
2. Move the Pointers: Adjust the pointers towards each other based on the given conditions.
3. Check Conditions: Continue moving the pointers toward each other until the desired result is found or a specific condition is met

Example:Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

def reverseWords(s: str) -> str:
    words = s.split()  # Split the input string into words

    for i in range(len(words)):
        left = 0  # Initialize the left pointer
        right = len(words[i]) - 1  # Initialize the right pointer
        split_word = list(words[i])  # Convert the word into a list of characters

        while left < right:  # Continue until the pointers meet in the middle
            # Swap the characters at the left and right pointers
            temp = split_word[left]
            split_word[left] = split_word[right]
            split_word[right] = temp

            left += 1  # Move the left pointer to the right
            right -= 1  # Move the right pointer to the left

        words[i] = "".join(split_word)  # Rejoin the characters into a word

    return " ".join(words)  # Join the reversed words into a final string

Pointers moving in the same direction.

In this approach, both pointers start from the same end of the data structure and move in the same direction. This technique is often used when you need to track a window or sub-array within an array, allowing you to efficiently move and adjust the window based on certain conditions. Common use cases include the sliding window technique and merging sorted arrays.

Approach

1. Initialize Two Pointers: Start with both pointers at the beginning of the data structure.
2. Move the Pointers: Move one pointer (usually the faster one) ahead of the other based on specific conditions.
3. Adjust the Pointers: Modify the positions of the pointers as needed to maintain the desired window conditions.

Example:You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

def mergeAlternately(word1: str, word2: str) -> str:
    # Initialize an empty list to store the merged characters
    word_list = []

    # Initialize two pointers, starting at the beginning of each word
    pointer_1 = 0
    pointer_2 = 0

    # Loop until one of the pointers reaches the end of its respective word
    while pointer_1 < len(word1) and pointer_2 < len(word2):
        # Append the character from word1 at pointer_1 to the list
        word_list.append(word1[pointer_1])
        # Append the character from word2 at pointer_2 to the list
        word_list.append(word2[pointer_2])

        # Move both pointers forward by one position
        pointer_1 += 1
        pointer_2 += 1

    # If there are remaining characters in word1, add them to the list
    if pointer_1 < len(word1):
        word_list.append(word1[pointer_1:])

    # If there are remaining characters in word2, add them to the list
    if pointer_2 < len(word2):
        word_list.append(word2[pointer_2:])

    # Join the list of characters into a single string and return it
    return "".join(word_list)

Conclusion

The two-pointer technique is a versatile and efficient tool in the world of algorithms, especially when dealing with arrays, strings, and linked lists. Whether the pointers are moving towards each other or in the same direction, this approach can simplify complex problems and improve the performance of your solutions. By understanding and applying these strategies, you'll be better equipped to tackle a wide range of coding challenges.

I encourage you to practice these techniques by solving various problems and experimenting with different scenarios. With time and experience, you'll find the two-pointer technique to be an invaluable addition to your problem-solving toolkit.

The above is the detailed content of Dissecting the two pointer technique. For more information, please follow other related articles on the PHP Chinese website!