LESSON 41/53Ready-made Containers

Two Pointers

GOALClose in from both ends of a sorted array to find a pair.

"Are there two numbers adding to exactly S?" A double loop makes that O(n²). But if the array is sorted you can start at both ends: too big, move the right pointer left; too small, move the left pointer right. One pass and you are done.

ON THIS PAGE

The example
Line by line
Watch it run
The other shapes this takes
When it needs sorted data
Common mistakes
Key words
Quick check
Now you try

SHOW EXAMPLE IN

//THE EXAMPLE

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 3, 4, 7, 11};
    int target = 10;

    int lo = 0, hi = (int)v.size() - 1;
    bool found = false;
    while (lo < hi) {
        int sum = v[lo] + v[hi];
        if (sum == target) {
            cout << v[lo] << " " << v[hi] << endl;
            found = true;
            break;
        }
        if (sum < target) lo++;
        else hi--;
    }
    if (!found) cout << "none" << endl;
    return 0;
}

> what you see

3 7

Try this code

//LINE BY LINE

int lo = 0, hi = (int)v.size() - 1;

Two pointers — one on the smallest, one on the largest.

if (sum < target) lo++;

Too small, so we need a bigger number: move the left pointer right.

else hi--;

Too big, so we need to shrink it: move the right pointer left.

while (lo < hi) {

<, not <=: an element must not be paired with itself.

Watch it run

A sorted array. lo starts at the left end, hi at the right.

1 / 6

The other shapes this takes

Closing in from both ends is only one shape. Two pointers can also move the same way together, making a sliding window.

Shape	Used for
Хоёр захаас дунд руу / Both ends inwards	Нийлбэр нь S болох хос / a pair adding to S
Хоёулаа урагш / Both moving forward	Хамгийн урт хэсэг / longest run with a property
Нэг нь хурдан, нэг нь удаан / One fast, one slow	Дундажийг олох, мөчлөг илрүүлэх / finding the middle, detecting a cycle

The gain is always the same: each pointer crosses the array ONCE. That is what turns O(n²) into O(n).

When it needs sorted data

The closing-in shape leans on the data being SORTED: "the sum is too big" only tells you to move the right pointer if the values are in order.

Shape	Needs sorting?
Хоёр захаас дунд руу / Both ends inwards	Тийм / yes
Хөдлөх цонх / Sliding window	Үгүй / no
Хурдан ба удаан / Fast and slow	Үгүй / no

Sorting costs O(n log n), slower than the O(n) walk itself. It is still far faster than the O(n²) you replaced.

//COMMON MISTAKES

✗ wrong

Эрэмбэлэгдээгүй массив дээр / On an unsorted array

✓ right

Эхлээд эрэмбэл / Sort it first

"Too big, shrink it" is only a valid move when the data is ordered.

✗ wrong

while (lo <= hi)

✓ right

while (lo < hi)

When they meet both point at the same element, and adding it to itself is usually wrong.

//KEY WORDS

two pointers

Two indices moving along one array together.

//QUICK CHECK

The sum is too BIG. Which pointer moves?

//NOW YOU TRY

Count how many PAIRS in a sorted array add up to S.

Open editor

Priority Queue Greedy

All lessons

LESSON 41/53Ready-made Containers

Two Pointers

GOALClose in from both ends of a sorted array to find a pair.

ON THIS PAGE

The example
Line by line
Watch it run
The other shapes this takes
When it needs sorted data
Common mistakes
Key words
Quick check
Now you try

SHOW EXAMPLE IN

//THE EXAMPLE

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {1, 3, 4, 7, 11};
    int target = 10;

    int lo = 0, hi = (int)v.size() - 1;
    bool found = false;
    while (lo < hi) {
        int sum = v[lo] + v[hi];
        if (sum == target) {
            cout << v[lo] << " " << v[hi] << endl;
            found = true;
            break;
        }
        if (sum < target) lo++;
        else hi--;
    }
    if (!found) cout << "none" << endl;
    return 0;
}

> what you see

3 7

Try this code

//LINE BY LINE

int lo = 0, hi = (int)v.size() - 1;

Two pointers — one on the smallest, one on the largest.

if (sum < target) lo++;

Too small, so we need a bigger number: move the left pointer right.

else hi--;

Too big, so we need to shrink it: move the right pointer left.

while (lo < hi) {

<, not <=: an element must not be paired with itself.

Watch it run

A sorted array. lo starts at the left end, hi at the right.

1 / 6

The other shapes this takes

Closing in from both ends is only one shape. Two pointers can also move the same way together, making a sliding window.

Shape	Used for
Хоёр захаас дунд руу / Both ends inwards	Нийлбэр нь S болох хос / a pair adding to S
Хоёулаа урагш / Both moving forward	Хамгийн урт хэсэг / longest run with a property
Нэг нь хурдан, нэг нь удаан / One fast, one slow	Дундажийг олох, мөчлөг илрүүлэх / finding the middle, detecting a cycle

The gain is always the same: each pointer crosses the array ONCE. That is what turns O(n²) into O(n).

When it needs sorted data

The closing-in shape leans on the data being SORTED: "the sum is too big" only tells you to move the right pointer if the values are in order.

Shape	Needs sorting?
Хоёр захаас дунд руу / Both ends inwards	Тийм / yes
Хөдлөх цонх / Sliding window	Үгүй / no
Хурдан ба удаан / Fast and slow	Үгүй / no

Sorting costs O(n log n), slower than the O(n) walk itself. It is still far faster than the O(n²) you replaced.

//COMMON MISTAKES

✗ wrong

Эрэмбэлэгдээгүй массив дээр / On an unsorted array

✓ right

Эхлээд эрэмбэл / Sort it first

"Too big, shrink it" is only a valid move when the data is ordered.

✗ wrong

while (lo <= hi)

✓ right

while (lo < hi)

When they meet both point at the same element, and adding it to itself is usually wrong.

//KEY WORDS

two pointers

Two indices moving along one array together.

//QUICK CHECK

The sum is too BIG. Which pointer moves?

//NOW YOU TRY

Count how many PAIRS in a sorted array add up to S.

Open editor

Priority Queue Greedy