Skip to main content

Read / Write Heads

Two pointers walk the same array in the same direction: a read head scans every element, and a write head marks where the next kept element belongs. Whatever the read head decides to keep gets written at the write head, which only then advances - so the prefix [0, write) is always the compacted answer.

Remove Elements​

27. Remove Element​

Easy·
2 Approachesclick to switch
Explanation

Remove every occurrence of val in-place and return the count of remaining elements. The array need not be in any particular order after the operation, and elements beyond the returned count are irrelevant.

Two-pointer approach:

  • A read pointer sweeps every index from left to right.
  • A write pointer tracks where the next kept element should land.
  • Whenever nums[read] differs from val, it is copied to nums[write] and write advances. Values equal to val are simply skipped - read moves on but write stays put, effectively overwriting them on the next keep.

Result:

  • After the loop, write equals the number of kept elements. The first write entries of nums hold those elements; the caller ignores the rest.

This is the classic overwrite variant: all kept elements slide to the front in their original relative order. No swaps are needed, making it particularly clean.

Analysis
Time
O(N)
  • N is the length of the input array. The read pointer visits every element exactly once.
Space
O(1)
  • Only two index variables are used regardless of input size.
FIG. 27 REMOVE ELEMENT● INTERACTIVE
visualization loads as you reach it
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
read = write = 0
while read < n:
if nums[read] != val:
nums[write] = nums[read]
write += 1
read += 1
return write

283. Move Zeroes​

Easy·
2 Approachesclick to switch
Explanation

Move all zeroes to the end of the array while preserving the relative order of non-zero elements, in-place and without returning a new array.

Phase 1 - Compact:

  • A read pointer scans every element; a write pointer marks the next open slot.
  • Non-zero elements are copied to nums[write] and write advances. Zeroes are skipped entirely.
  • After this pass, nums[0..write-1] holds all non-zero values in their original order.

Phase 2 - Zero-fill:

  • write then sweeps from its current position to n-1, writing 0 into every remaining slot.
  • This is necessary because the compact phase overwrites but never erases what it left behind.

Why two phases? This approach separates concerns cleanly: the first pass focuses on extracting keepers, the second on filling the tail. It is intuitive but does two partial passes over the array.

Analysis
Time
O(2n)
  • n = len(nums). Phase 1 (read loop) visits every element once - O(n). Phase 2 (write loop) visits at most n remaining slots - another O(n). Two separate passes give 2n.
Space
O(1)
  • Only the two index variables read and write; the operation is done in-place.
FIG. 283 MOVE ZEROES● INTERACTIVE
visualization loads as you reach it
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
n = len(nums)
read = write = 0
while read < n:
if nums[read] != 0:
nums[write] = nums[read]
write += 1
read += 1
 
while write < n:
nums[write] = 0
write += 1

1119. Remove Vowels from a String​

Easy·
Explanation

Filter out all vowels from a string, keeping consonants in their original order. Because Python strings are immutable, the input is first converted to a list so elements can be overwritten in-place.

Read / Write Heads:

  • The read head scans every character from left to right.
  • When s[read] is not a vowel (i.e., not in {'a', 'e', 'i', 'o', 'u'}), it is copied to s[write] and write advances.
  • When s[read] is a vowel, read moves on but write stays - the vowel is effectively discarded.

Result:

  • After the loop, s[:write] contains only the consonants in their original order.
  • "".join(s[:write]) reassembles them into a string.

The vowels set gives O(1) lookup per character. The in-place overwrite means no extra list allocation beyond the initial list(s) conversion.

Analysis
Time
O(N)
  • N is the length of the input string. The read pointer visits every character exactly once. Each visit does an O(1) set membership check.
Space
O(N)
  • Converting the immutable string to a list requires O(N) space. The final join also constructs a new string of at most N characters.
FIG. 1119 REMOVE VOWELS FROM A STRING● INTERACTIVE
visualization loads as you reach it
class Solution:
def removeVowels(self, s: str) -> str:
s = list(s)
n = len(s)
read = write = 0
vowels = set("aeiou")
while read < n:
if s[read] not in vowels:
s[write] = s[read]
write += 1
read += 1
return "".join(s[:write])

Remove Elements from Sorted Array​

80. Remove Duplicates from Sorted Array II​

Medium·
Explanation

Allow each unique value to appear at most twice in a sorted array, in-place. This is the generic removeDuplicatesK helper instantiated with k = 2.

How it works: The generic helper keeps an element if the slot k positions behind the write head is strictly smaller than the current read value. With k = 2, that means: an element passes if the value two steps back in the kept region is smaller - i.e., we have not yet placed two copies of this value.

  • The first two elements (read < 2) always pass unconditionally.
  • For subsequent elements, nums[write - 2] < nums[read] ensures at most two copies land in the output.

Why delegate to the helper? The LeetCode problem (k=2) is a special case of the more general problem. Expressing it as removeDuplicatesK(nums, k=2) makes the relationship explicit and avoids duplicating the pointer logic.

Visualization note: The read and write pointers live inside the helper frame - the animation shows them working through nums as the helper executes.

Analysis
Time
O(n)
  • n is the length of nums - removeDuplicatesK makes a single left-to-right pass, advancing read once per element.
Space
O(1)
  • The array is modified in place using only the read and write index variables.
FIG. 80 REMOVE DUPLICATES FROM SORTED ARRAY II● INTERACTIVE
visualization loads as you reach it
def removeDuplicatesK(nums, k: int):
n = len(nums)
read = write = 0
while read < n:
if read < k or nums[write - k] < nums[read]:
nums[write] = nums[read]
write += 1
read += 1
return write
 
 
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
return removeDuplicatesK(nums, k=2)

26. Remove Duplicates from Sorted Array​

Easy·
Explanation

Remove all duplicates from a sorted array in-place so that each unique value appears exactly once. This is the generic removeDuplicatesK helper with k = 1.

How it works: With k = 1, the survival condition simplifies to: an element at read passes if the slot one position behind the write head holds a strictly smaller value (nums[write - 1] < nums[read]). Because the array is sorted, "strictly smaller" means "different value" - so exactly one copy of each unique element survives.

  • The first element (read < 1) always passes unconditionally.
  • For every subsequent element, it passes only if it differs from the most recently kept element.

Why this works on sorted input: All duplicates of a value appear consecutively. Once the first copy is written, every subsequent duplicate fails the nums[write - 1] < nums[read] check (they are equal, not strictly less) and is skipped.

Visualization note: The pointer motion is driven inside removeDuplicatesK - you will see read and write advance through nums as the helper runs.

Analysis
Time
O(n)
  • removeDuplicatesK walks read through all n elements once.
Space
O(1)
  • In-place with two index variables.
FIG. 26 REMOVE DUPLICATES FROM SORTED ARRAY● INTERACTIVE
visualization loads as you reach it
def removeDuplicatesK(nums, k: int):
n = len(nums)
read = write = 0
while read < n:
if read < k or nums[write - k] < nums[read]:
nums[write] = nums[read]
write += 1
read += 1
return write
 
 
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
return removeDuplicatesK(nums, k=1)

Sort the Array​

922. Sort Array By Parity II​

Easy·
Explanation

Rearrange an array so that every even-indexed position holds an even number and every odd-indexed position holds an odd number. The input is guaranteed to have equal counts of even and odd numbers.

Why plain left/right heads would infinite-loop: A naive approach that scans left to right and swaps misplaced pairs can loop forever: after a swap, neither pointer advances, and if the newly swapped-in value is also wrong, the same pair is re-examined indefinitely.

Dedicated lane heads: The trick is to give each parity its own dedicated scanning pointer that jumps by 2, staying within its lane:

  • write starts at index 0 (even lane) and steps by 2 - it looks for an odd number sitting in an even slot (a misplaced value).
  • read starts at index 1 (odd lane) and steps by 2 - it looks for an even number sitting in an odd slot (a misplaced value).
  • When write finds an odd at an even slot and read finds an even at an odd slot, they are each other's fix: swap them. Both advance by 2.
  • If write's slot already has an even number, write skips forward (advance by 2 without swapping).
  • If read's slot already has an odd number, read skips forward (advance by 2 without swapping).

Correctness: Because the input has exactly N/2 even and N/2 odd numbers, every misplaced even in the odd lane is paired with a misplaced odd in the even lane. The heads will always find their counterpart - no element is left stranded.

Result: The array is rearranged in-place and returned. Each pass through the loop either fixes two misplaced elements or skips one correctly placed element.

Analysis
Time
O(N)
  • N is the length of the array. read visits at most N/2 odd-lane positions; write visits at most N/2 even-lane positions. Combined, O(N) total steps.
Space
O(1)
  • In-place rearrangement with two index variables.
FIG. 922 SORT ARRAY BY PARITY II● INTERACTIVE
visualization loads as you reach it
class Solution:
def sortArrayByParityII(self, nums: List[int]) -> List[int]:
n = len(nums)
read, write = 1, 0
while read < n:
if nums[read] % 2 == 1:
read += 2
elif nums[write] % 2 == 0:
write += 2
else:
nums[read], nums[write] = nums[write], nums[read]
read += 2
write += 2
return nums