Opposite-end pointers

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

Opposite-end pointers bound an active region. Mirror checks and sorted-pair searches can use each comparison to discard one boundary. Prove the movement rule before implementing it.

Work through an example

For target 9 in [1,2,4,7,11], discard 11 after 1+11>9, then discard 1 after 1+7<9. The remaining 2+7 matches.

Time and space complexity

O(n) time/O(1) space after sorting; each unsuccessful step narrows the interval.

Why it works

Every remaining valid pair lies within the active pointer interval.

Common mistakes

The sum rule fails on unsorted input.
left<right avoids using one position twice.

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