As part of my challenge to become better at coding interviews, today I learned the two-pointer technique. This algorithm uses two different pointers to solve a problem involving indices with the benefit of saving space and time.

In Computer Science, a pointer is a reference to an object.

When to use it

In many array problems, we have to analyze each element of the collection compared to its other elements.

There are many approaches to solving these problems and some might be iterating through the entire array one or more times depending on the way we implement code.

We may even need to implement a new data structure depending on the problem. These approaches may give the correct result but a more efficient solution is always preferred.

The two-pointer technique enables us to process two elements per loop as opposed to one.

This technique has some distinct patterns that include :

1. Two pointers, each starting from the beginning and the end until they both meet. An example problem that can be solved using this is return the indices of an array whose elements sum up to a target k assuming the array is sorted.
2. One pointer moving at a slow rate while the other moves at twice the speed. An example of a problem that can be solved with this technique is detecting cycles in a LinkedList

Examples

1. Return the indices in an array whose elements sum up to a target K

This problem is commonly referred to as two sum problem .

Here is the problem statement: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the target. The array is always sorted.

The brute force of this would be to find the sum of each element with the other and since there are n elements, this would give a quadratic time complexity.

Using the two-pointer approach, first create two pointers one to start off at the 0th index and the other to start from the end of the array.

function twoSum(nums, target) {
    let pointer1 = 0;
    let pointer2 = nums.length - 1;   
}

Next, we create a while loop that will keep running provided the first pointer, pointer1, is less than the second pointer,pointer2. Inside this while loop, we find the sum of the elements at the respective pointer positions. If the sum is equal to the target, return those two indices, otherwise, if the sum is less than the target, increase the first pointer position by one and if the sum is greater than the target, reduce the second pointer by 1.

while (pointer1 < pointer2) {
        let sum = nums[pointer1] + nums[pointer2];
        if (sum === target) {
            return [pointer1, pointer2];
        }
        else if (sum < target) {
            pointer1 += 1;
        }
        else {
            pointer2 -= 1;
        }
    }

The final code for this challenge is

function twoSum(nums, target) {
    let pointer1 = 0;
    let pointer2 = nums.length - 1;

    while (pointer1 < pointer2) {
        let sum = nums[pointer1] + nums[pointer2];
        if (sum === target) {
            return [pointer1, pointer2]
        }
        else if (sum < target) {
            pointer1 += 1;
        }
        else {
            pointer2 -= 1;
        }
    }
    return false
}

2.Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.

Here we apply the concept of having two pointers, a fast pointer that moves at twice the speed of the slow pointer. The idea is if these two pointers meet then there is a cycle, if the fast pointer reaches the end of the LinkedList without meeting with the slow one then the LinkedList has no cycle.

Here is the solution.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            return true
        }
    }
    return false;
};

There you have it Two Pointer Technique , be sure to consider using it in your next interview.