Opposite Ends

Escaping the Nested Loop

A brute-force pair search uses an outer loop to pick one element and an inner loop to check every other element.

That checks every pair, costing O(n²) time.

Opposite Ends is a Two Pointers pattern. One index starts at the beginning, another at the end, and both move toward the middle.

Each move rules out impossible pairs. Since each pointer travels in only one direction, the search usually finishes in O(n) time.

Placing the Two Pointers

Use an array sorted in increasing order, or a string whose two ends you need to compare.

Set left = 0 and right = n - 1. In Java or Python, these pointers are integer indexes.

Notice that left starts at the first cell and right starts at the last, with both directions leading toward the middle.

At each step, read the values at both positions and compare them.

Move one pointer inward according to that comparison. Continue while left < right, so the pointers converge and stop when they meet.

The Decision Rule

Begin with left at the first index and right at the last.

For sorted two-sum, add the values at those positions and compare the sum with the target.

Too small? Move left right to reach a bigger value. Too large? Move right left to reach a smaller value.

Equal? You found the pair. If the pointers meet first, no pair was found.

Tracing a Real Example

Array: [1, 3, 4, 6, 9]. Target: 9.

Start with left on 1 and right on 9. The sum is 10, too large, so right moves to 6.

Now 1 + 6 = 7, too small, so left moves to 3. Then 3 + 6 = 9. Done.

Only three comparisons were needed.

Why Nothing Gets Skipped

Sorting makes each pointer move safe.

When the sum is too small, left already holds the smallest remaining value. Pairing it with anything inside cannot produce a larger sum.

So that left value cannot be part of a valid pair, and left can move. The mirrored logic removes right when the sum is too large.

Without sorting, this elimination argument fails. With sorting, each pointer only moves inward, producing at most n moves and O(n) time.

Same Pattern, Other Problems

Each starts at opposite ends. The comparison changes, but the inward-moving shape stays.

Palindrome: compare both ends. Move both inward after a match; stop at a mismatch or when pointers meet.

Target sum: compare the sum with the target. Move one side, or stop when the sum equals the target.

Maximum area: compute the area between lines. Move the shorter line because it limits the height.

A scan ends at its result or when pointers meet. Each runs in O(n).

Spotting It in Your Work

Reach for Opposite Ends when you see a sorted array or a string and the problem asks about pairs or matching ends.

Ask two questions: What do I compare? Which side can I safely drop?

If both answers are clear, one inward scan can replace a nested loop, turning O(n²) into O(n).

Explain it plainly: start wide, compare, then shrink from the side that cannot help.

In the opposite-ends two-pointer approach on an array of length n, the right pointer starts at index _____

• n − 1
• n

Answer: n − 1

The left pointer starts at index 0 and the right pointer starts at the last valid index, n − 1. Index n is out of bounds.

In a sorted array two-sum search, if the current sum is too small, move the _____ pointer to the right. If the sum is too large, move the _____ pointer to the left.

Answer: In a sorted array two-sum search, if the current sum is too small, move the left pointer to the right. If the sum is too large, move the right pointer to the left.

Moving left rightward picks a larger value, increasing the sum. Moving right leftward picks a smaller value, decreasing the sum.

Sorted array [1, 3, 4, 6, 9], target 10. Pointers start at 1 and 9 (sum 10)... suppose instead the target is 12. The sum 1 + 9 = 10 is too small. What should happen next?

• Move left right, to the value 3
• Move right left, to the value 6
• Move both pointers inward at once
• Reset left to 0 and try the next right

Answer: Move left right, to the value 3

10 < 12, so you need a larger sum. Only moving left rightward (to 3) can increase it; 3 + 9 = 12 finds the pair. Moving right leftward would make the sum even smaller.