Remove Zero Readings From a Log, Then Do It In Place

Deleting each zero shifts everything after it, n times over; a read pointer and a write pointer copy each kept value once.

A read pointer and a write pointer filter an array in place in one pass, where deleting each unwanted value shifts every value after it. A sensor log holds the readings 3 0 0 8 0 5 7, and the zeros are moments the sensor was off. The task is to remove them in place, keeping the order of the rest, and to return how many readings remain.

The brute force deletes each zero where it stands. Deleting from the middle of an array shifts every later value one place left, which costs O(n) per deletion, so a log with mostly zeros costs O(n²). The repeated work is plain on this log: the 5 and the 7 are shifted three times each, once per zero before them, though each only needs to move once to its final place.

Two pointers move each kept value once. The read pointer visits every value in order. The write pointer marks the next slot a kept value should go into, starting at 0. When the read pointer finds a nonzero value, it is copied to the write pointer's slot and the write pointer moves on; a zero is skipped. The write pointer never passes the read pointer, so no value is overwritten before it has been read.

Deleting each zero against copying each kept value

DeletingO(n²) time

Each zero is removed where it is, and every value after it shifts one place left. A value is shifted once for every zero before it.

Read and write pointersO(n) time, O(1) extra space

Each nonzero value is copied once, to the write pointer's slot. Zeros are skipped and nothing shifts.

Followed value by value, the write pointer falls behind the read pointer at each zero and the kept values close up behind it.

Read and write pointers on 3 0 0 8 0 5 7

Inputreadings 3 0 0 8 0 5 7, keeping every nonzero value

Read 0
1. 3read
2. 0write
3. 0
4. 8
5. 0
6. 5
7. 7
3 kept: copied to slot 0, write moves to 1
Read 1
1. 3
2. 0readwrite
3. 0
4. 8
5. 0
6. 5
7. 7
0 skipped, write stays at 1
Read 2
1. 3
2. 0write
3. 0read
4. 8
5. 0
6. 5
7. 7
0 skipped, write stays at 1
Read 3
1. 3
2. 8
3. 0write
4. 8read
5. 0
6. 5
7. 7
8 kept: copied to slot 1, write moves to 2
Read 4
1. 3
2. 8
3. 0write
4. 8
5. 0read
6. 5
7. 7
0 skipped, write stays at 2
Read 5
1. 3
2. 8
3. 5
4. 8write
5. 0
6. 5read
7. 7
5 kept: copied to slot 2, write moves to 3
Read 6
1. 3
2. 8
3. 5
4. 7
5. 0write
6. 5
7. 7read
7 kept: copied to slot 3, write moves to 4

ResultThe write pointer ends at 4, so the first 4 slots hold the kept readings 3 8 5 7.

The listing runs both versions on the log and counts the work each does, then runs the two-pointer version on a log of zeros.

remove_zeros.pypy

def remove_by_deleting(readings: list[int]) -> int:
    shifted = 0
    i = 0
    while i < len(readings):
        if readings[i] == 0:
            shifted += len(readings) - i - 1
            del readings[i]
        else:
            i += 1
    return shifted


def remove_with_two_pointers(readings: list[int]) -> int:
    write = 0
    for read in range(len(readings)):
        if readings[read] != 0:
            readings[write] = readings[read]
            write += 1
    return write


log = [3, 0, 0, 8, 0, 5, 7]
deleted = list(log)
shifted = remove_by_deleting(deleted)
print("deleting:", *deleted, f"({shifted} values shifted)")
in_place = list(log)
kept = remove_with_two_pointers(in_place)
print("two pointers:", *in_place[:kept], f"({kept} values copied)")
print("whole array afterwards:", *in_place)
print("all zeros:", remove_with_two_pointers([0, 0, 0]))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

deleting: 3 8 5 7 (11 values shifted)
two pointers: 3 8 5 7 (4 values copied)
whole array afterwards: 3 8 5 7 0 5 7
all zeros: 0

Deleting shifted 11 values to keep 4, while the pointers copied each kept value once. The answer is the write pointer's final value, the kept length: the slots after it still hold old values, 0 5 7 here, and the caller ignores them. The pass is O(n) time and O(1) extra space for n readings, and a log of zeros keeps nothing and returns 0.

Two Pointer

← → move through sections and cards