How To Use The Two Pointer Technique

The two pointer technique is very efficient technique in software developers skills. You can use this technique and solve the problem faster and easier when you have a technical interview. I will cover the basics of this technique in this. I will try to explain how to use two variables pointing to different things. You can understand that when and how to use this technique. Hopefully you will be so comfortable to use this technique after this article.

What Is The Two Pointer Technique

As you understand the name of the technique that, you can use two different pointers for two different variables or references to keep track arrays or strings indexes. The reason we keep track of indexes or indices because it saves time and space. A lot of times problems with strings and arrays involve the comparison of two different elements. Referencing two pointer at the same time and iterating while referencing two at the time we have to cut down dramatically on the number of the operations that needs to occur.

In computer science a pointers is a reference to object. The object stores a memory address of another value located in computer memory in many programming languages. It’s a great wait the references to different object.

It’s simple like references as a variable to referencing an index. It could be also points to a node or an object. To keep it simple you can think of the diagram below.

If these are an array with element [1,2,3,4,5] and we have first pointer and second pointer. Imagine these pointer as a variables that storing Pointer1 = index 0, Pointer2 = index 4

When Do We Use It ?

In many problems involving collections such as arrays or list, we have to analyze each element of the collection compared to other elements.

There are many approaches to solving problems like these. For example we usually start from first index and iterate through the data structure one more or more times depending on the how we implement our code.

Sometimes we may even have to create an additional data structure depending on the problems requirements. This approach might give us the correct result, but it likely won’t give us the most space and time efficient result.

This is why the two-pointer technique is efficient. We are able to process two elements per loop instead of just one. Common patterns in the two- pointer approach entail:

1. Two pointers, each starting from the beginning and the end until they both meet.
2. One pointer moves at a slow pace, while the other pointer moves at twice the speed.

These patterns can be used for string or array questions. They can also be streamlined and made more efficient by iterating through two parts of an object simultaneously. You can see this in Two Sum problem or Reverse String problems.

Example

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6

Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

var twoSum = function (nums, target) {
    for (let i = 0; i < nums.length; i++) { 
        for (let j = i + 1; j < nums.length; i++) {
             nums[i] + nums[j] === target
             return [i, j]
        }
    }
};

Solution With Hash

var twoSum = function(nums, target) {
    let storage = {};
    for(let [index,num] of nums.entries()){
        if(storage[num]!== undefined) return [storage [num], index];
        storage[target- num ] = index
    }
 };

Explanation

Creating an object

Input: nums = [2,7,11,15], target = 9

Going to loop

as we iterate first time first time we will hit 2

index = 0

num = 2

if number 2 is exist in storage ? it doesn't in the storage now

so we will take target(9 ) — num(2) = index

storage = {

‘7’: 0

(key): value(index)

}

as we iterate second time first time we will hit 2

index = 1

num = 7

if number 7 is exist in storage ? YES IT DOES

so we are saying return the current index and the index we previous store in storage hash

[0,1]

[2,7] = 9

Solution With Map

We can also solve this problem in linear time. We have to create a map that keeps track of the element its own and index. What ever element we are on we will see if the difference between that element and target is in the map. If it is in in the map we will get our answer.

Let’s see the diagram and try to understand logic here

As you see the array above [2,5,7,4] and the target is 9.

We start with index 0 which is number 2

What number do we need to add number 2 to get the the Result 9

We need to add 7. Is 7 in the map? No.

We will add number 2 to the map.

Next we go number 5. What number we need to add to number 5 to get result 9 we need to add number 4 in the map.

Next we go number 7. What number do we need to get number 9 ?

We need number 2 which is in the map. That’s the answer.

Next step is, We have to push index of number 2 index: 0 and current element on push to index into the array and here is the result as [0,2]

Let’s see How we implement our solution with code.

var twoSum = function (nums, target) {
     let numberIndex = new Map();
     let result = [];
     for (let i = 0; i < nums.length; i++) {
      let num = nums[i];
      let complement = target - num;
      if (numberIndex.has(complement)) {
       result[0] = numberIndex.get(complement)
       result[1] = i;
         return result;
}
      numberIndex.set(num, i)
}
}