Dissecting the two pointer technique

Charles Amakoye — Sat, 10 Aug 2024 21:03:47 +0000

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

Initialize the Pointers: Start with one pointer at the beginning (left) and the other at the end (right) of the data structure.
Move the Pointers: Adjust the pointers towards each other based on the given conditions.
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

Initialize Two Pointers: Start with both pointers at the beginning of the data structure.
Move the Pointers: Move one pointer (usually the faster one) ahead of the other based on specific conditions.
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.

Three ways of accessing string characters in JavaScript

Charles Amakoye — Fri, 01 May 2020 05:22:19 +0000

How do we access characters in a string? Well, in this post we look at three ways that we can use to access a character at a particular index, i, in a string. In a string characters are indexed from left to right. For instance, in a string named str the first character is at index 0, while the last is at index str.length-1

1. using charAt() method

This method will return the character at a specified index in a string. The method takes in a parameter, an integer that represents the index of the character to be returned. The syntax for usage is string.charAt(index).

let str = 'string';
console.log(str.charAt(0)); // s

If no character is found, the method returns an empty string.

let str = 'string';
console.log(str.charAt(999)); // ''

2. using square brackets notation []

Another way of accessing a character in a string is to using the square bracket. for example;

let str = 'string';
console.log(str[1]); // t

When we try to access a character whose index is larger than the string length, the Square brackets [] returns undefined.

let str = 'string';
console.log(str[999]); // undefined

3. using for...of loop

We can also access string characters by simply iterating over its characters using the for...of loop

let str = 'string';
for(let char of str){
console.log(char); //s,t,r,i,n,g
}

Forem: Charles Amakoye

Dissecting the two pointer technique

Introduction.

Two pointers.

Types of two pointers.

Pointers moving towards each other.

Approach

Pointers moving in the same direction.

Approach

Conclusion

Three ways of accessing string characters in JavaScript

1. using charAt() method

2. using square brackets notation []

3. using for...of loop