Duplicate handling and partitioning

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

Duplicate rules depend on the requested output: unique values, unique tuples, or all index combinations. Partitioning divides input into predicate-based regions and need not be stable.

Work through an example

For unique three-sum, sort, fix one value, pair-search the suffix, then skip repeated fixed/pointer values after recording a match.

Time and space complexity

Three-sum O(n²) after sorting; two-way partition O(n) time/O(1) extra space.

Why it works

Each produced value tuple is unique under the skip rule; each partition region satisfies its predicate.

Common mistakes

Skipping before recording a match can lose it.
A set cannot repair incorrect pointer movement.

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