Sorted-pair search

What is the two-pointer technique?

A pointer in this technique is a variable holding a position in a sequence. Two pointers track two positions, and a rule tells you which one to move. This can avoid checking every possible pair. The rule must follow from the problem: being able to move two positions does not by itself make a solution correct.

Example: To check whether "abba" reads the same backwards, compare the first and last characters, then move both positions inward and compare again.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays Strings

Understand the idea

Sorted order makes sum comparisons monotone. Too small eliminates the smallest value; too large eliminates the largest. Carry original positions through a sort if the caller needs them.

Work through an example

For [1,3,4,6], target 8: sums 7,9,7 exhaust the interval without a pair. Returning None is correct.

Time and space complexity

O(n) search; general sorting adds O(n log n), plus storage depending on implementation.

Why it works

No eliminated boundary can combine with any remaining partner to reach the target.

Common mistakes

Sorting changes order.
Fixed-width sum overflow can corrupt comparisons.

Chapter lab · Python implementation

Pointer movement saves work only when it safely eliminates candidates. The lab searches sorted input; compaction shows a second use where read and write move in the same direction. Include any sorting cost in your answer and preserve original indices if the output contract requires them.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def sorted_pair(values,target):
    left,right=0,len(values)-1
    while left<right:
        total=values[left]+values[right]
        if total==target:
            return left,right
        if total<target:
            left+=1
        else:
            right-=1
    return None

def move_zeroes(values):
    write=0
    for read in range(len(values)):
        if values[read]!=0:
            values[write]=values[read]
            write+=1
    for i in range(write,len(values)):
        values[i]=0

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert sorted_pair([1,2,4,7,11],9)==(1,3)
assert sorted_pair([3,3],6)==(0,1)
assert sorted_pair([],1) is None
x=[0,1,0,3,12]; move_zeroes(x); assert x==[1,3,12,0,0]

CHECK YOUR UNDERSTANDING