DEV Community

Cover image for Two Pointer Method to find two numbers
Kunal Agrawal
Kunal Agrawal

Posted on

Two Pointer Method to find two numbers

Consider a situation, problem where you need to find a pair of numbers whose sum can give you a target number.
like, x+y = target
Here, you need to find x,y from array, list, vector or any other sequential data structure, where array is sorted.

Brute-force Approach

  1. Take one element and add it with another element.
  2. Do this until sum of these elements is equal to target. therefore, in worst case it will take

Time Complexity - O(n^2)

Two Pointer Method

  1. Take two variables start and end.
  2. Point start towards first element of array.
  3. Point end towards last element of array.
  4. Now let's put a while loop till we get desired result, condition - start + end == target.
  5. If start + end > target we will shift end leftwards.
  6. If start + end < target we will shift start rightwards.

Thus by using this technique we can solve this problem in
Time Complexity - O(n)

// Program to get two numbers from array whose sum is equal to target element.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[10] = {1, 4, 6, 8, 9, 12, 14, 16, 17};
    int target = 20, start = 0, end = 8;
    while ((a[start] + a[end] != target) && (start < end))
    {
        if (a[start] + a[end] > target)
        {
            end--;
        }
        else
        {
            start++;
        }
    }
    cout << "Two numbers are: " << a[start] << ", " << a[end] << endl;
    return 0;
}

// Code contributed by Kunal Agrawal
Enter fullscreen mode Exit fullscreen mode

Thanks for reading this article.
Have a great day! 🙂

Top comments (0)