templates · Two pointers, windows & prefix sums

Two pointers (read / write)

  • "Remove" or "keep" some elements in place and return the new length
  • "Do not allocate extra space" (O(1) memory) on an array
  • Keep the order of the kept elements, like a filter

Two pointers (read / write)

the one rule

The invariant

nums[0..write) always holds exactly the kept elements seen so far, in their original order.

write it from memory

The template

keep what you want, copy it forward

javajava.util.*
/** Keep the elements you want, in order, at the front. Returns how many were kept. Example: remove duplicates (sorted). */static int keepWanted(int[] nums) {    int write = 0;                                    // nums[0..write) is the answer so far    for (int read = 0; read < nums.length; read++) {  // read looks at every element once        if (write == 0 || nums[read] != nums[write - 1]) { // keep this one?            nums[write] = nums[read];                 // copy it to the write spot            write++;        }    }    return write;                                     // new length}

Think of read as the reader and write as the pen. The pen only moves when you keep something.

fill in the blanks — only these lines change per problem

  1. line 5The keep rule: not a duplicate, not equal to val, not zero…
  2. line 6Copy or swap. Copy if the tail does not matter; swap if the unwanted elements must stay.
  3. line 10What to return: usually write, the new length.

each value at most k times

javajava.util.*
/** Same skeleton, allowing each value at most k times (sorted input). k = 2 → LeetCode 80. */static int keepAtMostK(int[] nums, int k) {    int write = 0;    for (int read = 0; read < nums.length; read++) {        if (write < k || nums[read] != nums[write - k]) { // compare with k places back            nums[write++] = nums[read];        }    }    return write;}

Compare with nums[write - k], the element k places back in the answer, not in the input.

fill in the blanks — only these lines change per problem

  1. line 5The k in nums[write - k]: 1 for plain dedup, 2 for "at most twice".

swap instead of copy

javajava.util.*
/** Move every wanted element to the front by swapping, so the rest end up at the back. Example: move zeroes. */static void moveWantedToFront(int[] nums) {    int write = 0;    for (int read = 0; read < nums.length; read++) {        if (nums[read] != 0) {                        // wanted = non-zero            int tmp = nums[write];                    // swap keeps the unwanted ones            nums[write] = nums[read];            nums[read] = tmp;            write++;        }    }}

Swapping keeps the unwanted elements at the back, so nothing is lost. Move zeroes uses this.

complexity

What it costs

time O(n)
read visits each element once; write only moves forward.
space O(1)
The answer is written over the input itself.

watch out

Common bugs

  • In the at-most-k version, comparing with nums[read - k] instead of nums[write - k]. Earlier writes may have overwritten that cell, so you compare with the wrong value.
  • Returning write - 1 or write + 1. The kept part is [0, write), so its length is exactly write.
  • Using copy when the problem needs the removed elements at the end (move zeroes). Use the swap version then.

use it

Practise it on

learn it properly