Removing, moving or deduplicating values without allocating another full collection.
- modify the same array
- preserve relative order
- return the new valid length
Positions before write contain exactly the valid values encountered so far, in original order.
O(n) time. Typical auxiliary space: O(1).
JAVA STARTING POINT
A template to adapt, not memorize.
int write = 0;
for (int read = 0; read < values.length; read++) {
if (shouldKeep(values[read])) {
values[write++] = values[read];
}
}Common mistakes
- Advancing write for rejected values
- Reading overwritten data
- Returning the last index instead of the length
PUBLISHED / 03
Learn in this order.
Available articles always appear before the publishing plan.
Two Pointers in Java: A Beginner's Guide
Learn two pointers through palindrome checks, sorted pair sums, duplicate removal, merging, and fast/slow linked-list examples, with diagrams and explained Java code.
Read article →Remove Duplicates from a Sorted Array
Use read and write pointers to keep one copy of each value in place.
Read article →Move Zeroes to the End
Move every zero to the end while preserving the order of nonzero values.
Read article →PLANNED PRACTICE
What comes after the published lessons.
- Remove a chosen valuePlanned, not yet published
- Keep at most two duplicatesPlanned, not yet published
