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.

Sources: Wikipedia: In-place algorithm

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
}

declare function shouldKeep(candidate: number, kept: number): boolean;

function compact(arr: number[]): number {
    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
}

def compact(arr):
    slow = 0
    for fast in range(len(arr)):
        if should_keep(arr[fast], arr[slow]):
            arr[slow] = arr[fast]
            slow += 1
    return slow  # new length

function compact(array &$arr): int {
    $slow = 0;
    for ($fast = 0; $fast < count($arr); $fast++) {
        if (shouldKeep($arr[$fast], $arr[$slow])) {
            $arr[$slow] = $arr[$fast];
            $slow++;
        }
    }
    return $slow; // new length
}

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

    private static boolean shouldKeep(int candidate, int kept) {
        throw new UnsupportedOperationException("your rule here");
    }

    public static int Compact(int[] arr) {
        int slow = 0;
        for (int fast = 0; fast < arr.Length; fast++) {
            if (ShouldKeep(arr[fast], arr[slow])) {
                arr[slow] = arr[fast];
                slow++;
            }
        }
        return slow; // new length
    }

    private static bool ShouldKeep(int candidate, int kept) {
        throw new NotImplementedException("your rule here");
    }

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)?

Use Two pointers (same direction) when the problem statement says “remove duplicates in place, keep order”, “move/partition elements while preserving order” or “compact an array and use O(1) extra space”. A solution built on it usually runs in O(n).

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Two pointers (same direction) confused with?

Two pointers (same direction) is most often confused with In-place array transform, Two pointers (opposite ends), Sliding window (variable) and Fast & slow pointers.

• 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

  Shifting the tail on each removal turns a linear pass into O(n squared) work. One forward copy per keeper is enough.

• Trusting the slots past write

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

Which interview problems use Two pointers (same direction)?

Interview problems solved with Two pointers (same direction) include Remove duplicates from sorted array, Remove element, Move zeroes, Remove duplicates from sorted array II, String compression, Is subsequence and Merge sorted array.

• 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)?

The target complexity of Two pointers (same direction) is O(n).

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