Two pointer trick JavaScript program

Double pointer technology for JavaScript programs is a commonly used algorithmic method used to solve various problems that require linear time complexity. This technique is widely used in the solution of problems that find, sort, or manipulate arrays, strings, or linked lists. This method works by maintaining two pointers, one starting from the beginning of the data structure and the other starting from the end, and then iterating through them in the opposite direction until a solution is found.

In this tutorial, we will explore the concept of double pointer technology and how to implement it using the JavaScript programming language. So let's start with the problem statement first and then move forward with this fun tutorial!

Problem Statement

Given an array A sorted in ascending order, containing N integers, check whether there is any pair of elements (A[i], A[j]) such that their sum equals X.

Now let us understand the role of the above program through some examples.

Input: const array = [1, 3, 5, 7, 9];
   const X = 12;
Output: Pair found at indices 1 and 4

Explanation − In this case, the element pair (3, 9) in the input array is added to give the target sum 12, and the program correctly identifies the element pair with index 1 and 4.

Input: const array = [1, 3, 5, 7, 9];
   const X = 9;
Output: Pair not found

Explanation − In this case, if the target sum is 9, then no such pair exists and the function should return "pair not found".

algorithm

Algorithm using double pointer trick to find whether there is a pair of elements in a sorted array whose sum is equal to the given target value -

• Initialize two pointers, left = 0, right = array length - 1.

• When the left side is smaller than the right side, perform the following operations

  • Calculate the sum of the elements at index left and right.

  • If the sum is equal to the target value, return the left index and right index.

  • If the sum is less than the target value, increase the left.

  • If the sum is greater than the target value, decrease the right side.

• If such a pair does not exist, return null.

The above algorithm uses double pointer technology to search a pair of elements in a sorted array so that their sum is equal to the given target value. The pointers start at either end of the array and move toward each other based on how the sum of the elements at the pointer compares to the target value. If the sum is less than the target value, move the left pointer to the right to increase the sum. If the sum is greater than the target value, move the right pointer to the left to decrease the sum. If the sum is equal to the target value, the program returns the index of the pair of elements. If no such pair of elements exists, the program returns Pair Not Found.

Now let us understand this algorithm through an example, in this example we will use JavaScript to implement the problem statement discussed earlier.

The Chinese translation of

Example

is:

Example

In this program, we used the Two Pointers Technique to find whether there exists a pair of elements in a given sorted array whose sum equals a given target. By iterating through the array and moving the pointers based on the sum of the elements at the pointers, the program efficiently finds the pair of elements (if it exists) in O(N) time complexity, where N is the number of elements in the array.

function findSumPair(array, X) {
   let left = 0;
   let right = array.length - 1;
   while (left < right) {
      const sum = array[left] + array[right];
      if (sum === X) {
         console.log(`Pair found at indices ${left} and ${right}`);
         return [left, right];
      } else if (sum < X) {
         left++;
      } else {
         right--;
      }
   }
   console.log('Pair not found');
   return null;
}
const array = [1, 3, 5, 7, 9];
const X = 12;
console.log(`Array: ${array}`);
console.log(`Target sum: ${X}`);
findSumPair(array, X);

in conclusion

In this tutorial, we explored the concept of double pointer technique and how to implement it using the JavaScript programming language to solve problems involving searching or comparing a pair of elements in a sorted array. We also learned an algorithm for finding a pair of elements such that their sum equals a given target using the two-pointer technique. By using this technique, we can significantly improve the efficiency of our program in terms of time complexity. Specifically, the double-pointer technology can solve this type of problem in a time complexity of O(N), which is much faster than the brute force method of O(N^2). Therefore, it is very important to learn and apply this technique to solve similar problems efficiently.

The above is the detailed content of Two pointer trick JavaScript program. For more information, please follow other related articles on the PHP Chinese website!