Same-direction read/write 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

Same-direction pointers separate inspection from output. Read visits every input; write advances only when retaining a value. This supports stable filtering without repeatedly shifting deleted elements.

Work through an example

Moving zeros in [0,1,0,3,12] first writes [1,3,12] into the prefix, then fills the suffix with zeros.

Time and space complexity

O(n) time/O(1) auxiliary space; input mutation is intentional.

Why it works

The written prefix equals all retained processed values in order, and write≤read.

Common mistakes

Do not write zeros before all original input is read.
A valid-prefix contract differs from a full-list result.

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