Maintaining a pointer invariant

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

An invariant relates pointer state to the original goal. Prove initialization, preservation, progress, and termination. It must justify both what is retained and what is eliminated.

Work through an example

In sorted pair search, discarded boundaries cannot participate in a valid remaining pair. When left≥right there are fewer than two candidates.

Time and space complexity

Progress decreases right-left by one each unsuccessful iteration, bounding total work by O(n).

Why it works

All not-yet-eliminated solutions remain in the active interval.

Common mistakes

Movement by intuition can skip a solution.
A claimed invariant must hold before every iteration.

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