Two pointers (same direction)

How does Two pointers (same direction) work?

Both indices start at the front of the array. read scans, and write marks the next output slot.

read advances once per loop step. It looks at every element exactly one time.

A test decides whether the current value is kept. That test is the only part that changes per problem.

On a keep, the value is copied into slot write. Then write advances by one.

On a drop, write stands still. The slot waits for the next value that survives.

write trails read by the number of drops so far. So the prefix up to write is the answer.

1. [3, 2, 3, 4, 2] write=0Every 3 has to go. arr[0] is a 3, so nothing is written.
2. [2, 2, 3, 4, 2] write=1arr[1] is a 2 and survives. It is copied into slot 0.
3. [2, 2, 3, 4, 2] write=1arr[2] is another 3. write stays where it was.
4. [2, 4, 3, 4, 2] write=2arr[3] is a 4 and survives. It lands in slot 1.
5. [2, 4, 2, 4, 2] write=3The last 2 lands in slot 2. The answer is length 3.

function compact(arr) {
    let slow = 0;
    for (let fast = 0; fast < arr.length; fast++) {
        if (shouldKeep(arr[fast], arr[slow])) {
            arr[slow] = arr[fast];
            slow++;
        }
    }
    return slow; // new length
}

A worked example of Two pointers (same direction)

Keep each value at most twice

A sorted array can repeat the same value many times. Trim it so no value appears more than twice.

Work inside the same array and return the new length.

The first two values are always fine, because two copies are allowed.

After that, keep arr[read] only when it differs from arr[write - 2]. That slot holds the second copy already written.

function removeDuplicatesII(nums) {
    let write = 0;

    for (let read = 0; read < nums.length; read++) {
        // nums[write - 2] is the copy two slots back in the output
        if (write < 2 || nums[read] !== nums[write - 2]) {
            nums[write] = nums[read];
            write++;
        }
    }

    return write; // new logical length
}

When should you use Two pointers (same direction)?

These phrases in a problem statement point here:

• •remove duplicates in place, keep order
• •move/partition elements while preserving order
• •compact an array and use O(1) extra space
• •shift zeros or a target value to the end

What is Two pointers (same direction) confused with?

• In-place array transform: Working in one buffer is the goal. A trailing write pointer is one way to reach it.
• Two pointers (opposite ends): Those pointers start at the ends of sorted data and converge. These both start at index zero.
• Sliding window (variable): A window also moves two indices forward, but it keeps a live span. Here the trailing index is a write slot.
• Fast & slow pointers: There the fast pointer takes two steps to catch a cycle. Here it takes one and reads.

Common mistakes with Two pointers (same direction)

• Letting write overtake read

  A copy would then destroy data read has not seen. write advances only on a keep.

• Testing against the source array

  The check belongs on arr[write - 1], the last value actually kept. arr[read - 1] may already be gone.

• Shifting the tail on every removal

  That turns a linear pass into O(n squared) work. One forward copy per keeper is enough.

• Trusting the slots past write

  They still hold stale values from before the pass. Only the first write slots mean anything.

Which interview problems use Two pointers (same direction)?

• Remove duplicates from sorted array: Keep a value only when it differs from arr[write - 1].
• Remove element: Keep every value that does not equal the target.
• Move zeroes: Copy the non-zeroes forward, then pad the tail.
• Remove duplicates from sorted array II: The check moves back two slots instead of one.
• String compression: Write the character, then write the length of its run.
• Is subsequence: One pointer walks the short string, one walks the long one.
• Merge sorted array: Write from the back so nothing unread is overwritten.

What is the time and space complexity of Two pointers (same direction)?

O(n)

n up to 1e6 gives O(n) time and O(1) space. The read pointer sees each element once.