DATA STRUCTURES AND ALGORITHMS

Two Pointers Technique

The two-pointer technique is a fundamental algorithmic approach that plays a pivotal role in optimizing solutions to specific types of problems in computer science. This strategy involves the use of two pointers, often represented as indices or references, that traverse a data structure, such as an array, list, or string, simultaneously. By manipulating the positions of these two pointers , the technique aims to efficiently address a wide range of problems, making it a valuable tool in a programmer’s toolkit.

There are several ways to implement two-pointers. To start, let’s look at the following method:

Start the pointers at the edges of the input. Move them towards each other until they meet.

Converting this idea into instructions:

1. Start one pointer at the first index 0 and the other pointer at the last index input.length - 1.
2. Use a while loop until the pointers are equal to each other.
3. At each iteration of the loop, move the pointers towards each other. This means either increment the pointer that started at the first index, decrement the pointer that started at the last index, or both. Deciding which pointers to move will depend on the problem we are trying to solve.

Here’s some pseudocode illustrating the concept:

function fn(arr):
    left = 0
    right = arr.length - 1

    while left < right:
        Do some logic here depending on the problem
        Do some more logic here to decide on one of the following:
            1. left++
            2. right--
            3. Both left++ and right--

The strength of this technique is that we will never have more than O(n) iterations for the while loop because the pointers start n away from each other and move at least one step closer in every iteration. Therefore, if we can keep the work inside each iteration at O(1), this technique will result in a linear runtime, which is usually the best possible runtime.

Let’s look at some of the use cases of this technique:

Example 1: Given a string s, return true if it is a palindrome, false otherwise.

A string is a palindrome if it reads the same forward as backward. That means, after reversing it, it is still the same string. For example: “abcdcba”, or “racecar”.

Method 1: Naïve Approach

The most straightforward way to check if a string is a palindrome is to reverse it and compare it to the original string. If they match, we have a palindrome. If not, the string is not a palindrome.

Pseudocode:

function isPalindrome(s):
    reversedS = reverse(s)
    if s == reversedS:
        return true
    else:
        return false

Explanation:

1. We start by reversing the input string s using a function reverse(s).
2. Then, we compare the original string s with the reversed string reversedS.
3. If they are identical, we return true, indicating that s is a palindrome. Otherwise, we return false.

JavaScript Code:

function isPalindrome(s) {
    // convert to lowercase
    s = s.toLowerCase();

    // Reverse the input string
    const reversedS = s.split('').reverse().join('');
    
    // Compare the original string with the reversed string
    return s === reversedS;
}

// Test cases
const string1 = "racecar";
const string2 = "Radar";

console.log(isPalindrome(string1)); // Output: true
console.log(isPalindrome(string2)); // Output: true

Complexity Analysis:

• Time Complexity: Reversing a string takes O(n) time, where n is the length of the string. The comparison also takes O(n) time. Therefore, the overall time complexity is O(n).
• Space Complexity: We need additional space to store the reversed string, which takes O(n) space. So, the space complexity is O(n).

The naïve approach provides a simple and intuitive way to check if a string is a palindrome. However, it has room for optimization, as we are using extra space and performing unnecessary comparisons

Method 2: Two Pointers Technique

The two-pointer technique is a clever strategy that leverages the fact that for a palindrome string, the first character is the same as the last character, the second character is the same as the second last character, and so on. By using two pointers, one starting from the beginning of the string and the other from the end, we can efficiently check if all corresponding characters are equal. If we find a mismatch at any point, we can immediately conclude that the string is not a palindrome.

JavaScript Code:

function isPalindrome(s) {
    let left = 0;             // Pointer starting from the beginning
    let right = s.length - 1; // Pointer starting from the end
    
    while (left < right) {
        // Compare the characters at the left and right pointers, ignoring case
        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false; // Mismatch found, not a palindrome
        }
        
        // Move the pointers towards each other
        left++;
        right--;
    }
    
    return true; // No mismatch found, it's a palindrome
}

// Test cases
const string1 = "racecar";
const string2 = "Radar";

console.log(isPalindrome(string1)); // Output: true
console.log(isPalindrome(string2)); // Output: true

Notice that if the input was an array of characters instead of a string, the algorithm wouldn’t change. The two-pointers technique works as long as the index variables are moving along some abstract iterable.

This algorithm is very efficient as not only does it run in O(n), but it also uses only O(1) space. No matter how big the input is, we always only use two integer variables. The time complexity is O(n) because the while loop iterations cost O(1) each, and there can never be more than O(n) iterations of the while loop — the pointers start at a distance of n from each other and move closer by one step each iteration.

Example 2: Given a sorted array of unique integers and a target integer, return true if there exists a pair of numbers that sum to target, false otherwise. This problem is similar to Two Sum. (In Two Sum, the input is not sorted).

For example, given nums = [1, 2, 4, 6, 8, 9, 14, 15] and target = 13, return true because 4 + 9 = 13.

Method 1: Brute Force Approach

The brute force approach involves checking all possible pairs of numbers in the sorted array to see if any of them add up to the target integer. Although this method is not the most efficient, it can serve as a baseline for understanding the problem.

Pseudocode:

function hasPairWithSum(nums, target):
    n = length of nums
    for i from 0 to n-2:
        for j from i+1 to n-1:
            if nums[i] + nums[j] == target:
                return true
    return false

Explanation:

1. We initialize a variable n to store the length of the input array nums.
2. We use two nested loops to iterate through all possible pairs of numbers in the array, represented by indices i and j.
3. For each pair, we check if the sum of nums[i] and nums[j] equals the target integer.
4. If a pair is found that satisfies the condition, we return true, indicating that there exists a pair with the desired sum.
5. If no such pair is found after checking all possible pairs, we return false.

JavaScript code:

function hasPairWithSum(nums, target) {
    const n = nums.length;

    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return true;
            }
        }
    }

    return false;
}

// Example usage:
const nums = [1, 2, 4, 6, 8, 9, 14, 15];
const target = 13;
const result = hasPairWithSum(nums, target);
console.log(result); // Output: true (4 + 9 = 13)

Complexity Analysis:

• Time Complexity: The brute force approach checks all possible pairs of numbers, resulting in a time complexity of O(n²), where n is the number of elements in the array.
• Space Complexity: The algorithm uses a constant amount of additional space, so the space complexity is O(1).

While this approach works, it may not be efficient for large input arrays due to its quadratic time complexity.

Method 2: Two Pointers Technique

Let’s use the example input. With two pointers, we start by looking at the first and last number. Their sum is 1 + 15 = 16. Because 16 > target, we need to make our current sum smaller. Therefore, we should move the right pointer. Now, we have 1 + 14 = 15. Again, move the right pointer because the sum is too large. Now, 1 + 9 = 10. Since the sum is too small, we need to make it bigger, which can be done by moving the left pointer. 2 + 9 = 11 < target, so move it again. Finally, 4 + 9 = 13 = target.

The reason this algorithm works: because the numbers are sorted, moving the left pointer permanently increases the value the left pointer points to (nums[left] = x). Similarly, moving the right pointer permanently decreases the value the right pointer points to (nums[right] = y). If we have x + y > target, then we can never have a solution with y because x can only increase. So if a solution exists, we can only find it by decreasing y. The same logic can be applied to x if x + y < target.

JavaScript Code:

function hasPairWithSum(nums, target) {
    let left = 0;             // Pointer starting from the beginning
    let right = nums.length - 1; // Pointer starting from the end
    
    while (left < right) {
        const sum = nums[left] + nums[right];
        
        if (sum === target) {
            return true; // Pair found, return true
        } else if (sum < target) {
            left++; // Move the left pointer to increase the sum
        } else {
            right--; // Move the right pointer to decrease the sum
        }
    }
    
    return false; // No pair found, return false
}

const nums = [1, 2, 4, 6, 8, 9, 14, 15];
const target = 13;

const result = hasPairWithSum(nums, target);
console.log(result); // Output: true (4 + 9 = 13)

This algorithm uses O(1) space and has a time complexity of O(n).

Another Two Pointer Technique approach

This method where we start the pointers at the first and last indices and move them towards each other is only one way to implement two pointers. Algorithms are beautiful because of how abstract they are — “two pointers” is just an idea, and it can be implemented in many ways. Let’s look at another method.

The following method is applicable when the problem has two iterables in the input, for example, two arrays.

Example 3: Given two sorted integer arrays arr1 and arr2, return a new array that combines both of them and is also sorted.

The trivial approach would be to first combine both input arrays and then perform a sort. If we have n = arr1.length + arr2.length, then this gives a time complexity of O(n⋅logn) (the cost of sorting). This would be a good approach if the input arrays were not sorted, but because they are sorted, we can take advantage of the two-pointers technique to improve to O(n).

Solution: Two-pointers technique

We can build the answer array ans one element at a time. Start two pointers at the first index of each array, and compare their elements. At each iteration, we have 2 values. Whichever value is lower needs to come first in the answer, so add it to the answer and move the respective pointer.

Javascript Code:

var combine = function(arr1, arr2) {
    // Initialize an empty array to store the merged result
    let ans = [];
    // Initialize two pointers for arr1 and arr2
    let i = 0, j = 0;
    
    // Loop until we reach the end of either arr1 or arr2
    while (i < arr1.length && j < arr2.length) {
        // Compare the current elements at arr1[i] and arr2[j]
        if (arr1[i] < arr2[j]) {
            // If arr1[i] is smaller, push it to the result and move the arr1 pointer
            ans.push(arr1[i]);
            i++;
        } else {
            // If arr2[j] is smaller or equal, push it to the result and move the arr2 pointer
            ans.push(arr2[j]);
            j++;
        }
    }
    
    // If there are remaining elements in arr1, append them to the result
    while (i < arr1.length) {
        ans.push(arr1[i]);
        i++;
    }
    
    // If there are remaining elements in arr2, append them to the result
    while (j < arr2.length) {
        ans.push(arr2[j]);
        j++;
    }
    
    // Return the merged and sorted array
    return ans;
}

Like in the previous two examples, this algorithm has a time complexity of O(n) and uses O(1) space (if we don’t count the output as extra space, which we usually don’t).

Concluding Remarks:

It’s crucial to recognize that the techniques discussed here serve as valuable guidelines rather than rigid rules. The specific problem you encounter may require a tailored approach. For instance, in the first method, we initiated the pointers at the first and last index, but some situations might demand a different starting point for the pointers. Similarly, the second method involves moving two pointers forward along separate inputs, but there are scenarios where you may deal with a single input, yet still start both pointers at the first index and advance them in tandem.

The term “two pointers” essentially refers to the utilization of two integer variables for traversing through iterable structures. While the strategies covered in this article are prevalent and effective, it’s essential to remain open to alternative problem-solving approaches. Some problems even necessitate the application of “three pointers” or similar variations.