Hello everyone!

Today I want to explain one of the most useful techniques in competitive programming — Two Pointers * What is Two Pointers?

Two pointers is a technique where we use two indices to iterate over an array or string.

Usually:

• One pointer starts from the beginning
• Another from the end (or also from beginning)

• Example Problem

Given an array, find if there exist two numbers whose sum equals k.

• Idea

1. Sort the array

2. Set:

   left = 0 right = n — 1

3. While left < right:

   if a[left] + a[right] == k → FOUND if sum < k → left++ if sum > k → right--

• Code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    int l = 0, r = n &mdash; 1;
    while(l < r) {
        int sum = a[l] + a[r];
        if(sum == k) {
            cout << "YES\n";
            return 0;
        }
        else if(sum < k) l++;
        else r--;
    }
    cout << "NO\n";
}

• Complexity

Sorting: O(n log n) Two pointers: O(n)

Total: O(n log n)

• When to Use?

1) Sorted arrays 2)Pair problems 3)Subarray problems

*Final Tip

If you see:

1) “find pair” 2) “sum equals k” 3) “continuous segment” Think about Two Pointers

Thanks for reading! If this helped you, please upvote