JuniorCodeCommonNot answered yet
Remove zeros from a vector preserving order in O(n)
Remove all zeros from a vector of integers, keeping the relative order of the remaining elements.
Requirements:
O(n²)).
- O(n) time, O(1) extra space — do not shift the tail on each removal (that is
void removeZeros(std::vector<int>& v) {
// your code here
}Write the implementation.
Use a write index. Walk the vector with a read index; for each non-zero element, copy it to the write position and advance the write index. After the pass, resize the vector to the write index. One pass, O(n) time, O(1) extra space. The idiomatic form is the erase-remove idiom: v.erase(std::remove(v.begin(), v.end(), 0), v.end()).
- ✗Calling
eraseper zero, shifting the tail each time and degrading to O(n²) - ✗Swap-with-last, which removes zeros but scrambles the order of the kept elements
- ✗Forgetting to resize/erase the leftover tail after compacting
- →What does
std::removeactually do to the tail, and why iserasestill needed? - →How would you instead move all zeros to the end, keeping non-zero order?
Contents
Task
Remove zeros from a vector, preserving order, in O(n) time and O(1) space.
Solution
void removeZeros(std::vector<int>& v) {
size_t write = 0;
for (size_t read = 0; read < v.size(); ++read)
if (v[read] != 0) v[write++] = v[read]; // keep non-zeros
v.resize(write); // truncate the tail
}
// Idiomatic form:
// v.erase(std::remove(v.begin(), v.end(), 0), v.end());Key points
- The write index compacts non-zero elements in one pass — order is preserved.
std::removeonly shifts elements; the trailingeraseis what changes the size.- Per-element
eraseshifts the tail each time and is O(n²).
Contents
