Array Compaction

Array compaction removes elements that do not satisfy a predicate by overwriting them with elements that do. It operates in-place and preserves the relative order of retained elements.

You use it when filtering data without allocating additional memory.

Problem

Given an array $A$ of length $n$ and a predicate $P(x)$, remove all elements that do not satisfy $P$, and return the new length.

After compaction:

• for all $i < k$, $P(A[i])$ holds
• indices $i \ge k$ are ignored

Algorithm

Use a write pointer to overwrite unwanted elements.

compact(A, P):
    k = 0

    for i from 0 to length(A) - 1:
        if P(A[i]):
            A[k] = A[i]
            k += 1

    return k

Example

Let

$$ A = [8, 3, 5, 2, 1, 4] $$

Keep even numbers:

$$ P(x): x \bmod 2 = 0 $$

step	i	value	action	array	k
1	0	8	keep	[8, 3, 5, 2, 1, 4]	1
2	1	3	skip	[8, 3, 5, 2, 1, 4]	1
3	2	5	skip	[8, 3, 5, 2, 1, 4]	1
4	3	2	keep	[8, 2, 5, 2, 1, 4]	2
5	4	1	skip	[8, 2, 5, 2, 1, 4]	2
6	5	4	keep	[8, 2, 4, 2, 1, 4]	3

Result:

$$ [8, 2, 4] $$

New length:

$$ k = 3 $$

Correctness

At each step:

• indices $[0, k-1]$ contain elements that satisfy $P$ in their original order
• indices $[k, i]$ may contain unprocessed or discarded elements

When $P(A[i])$ holds, writing it to position $k$ extends the valid prefix. Since elements are processed left to right, their order is preserved.

After the loop, the first $k$ elements form exactly the filtered array.

Complexity

operation	time
compaction	$O(n)$

Space usage:

$$ O(1) $$

When to Use

Array compaction is appropriate when:

• elements must be filtered in-place
• order must be preserved
• memory allocation should be avoided
• output size is smaller than input

It is less suitable when:

• original array must remain unchanged
• removed elements must be preserved elsewhere

Implementation

def compact(a, predicate):
    k = 0
    for i in range(len(a)):
        if predicate(a[i]):
            a[k] = a[i]
            k += 1
    return k

func Compact[T any](a []T, pred func(T) bool) int {
    k := 0
    for i := 0; i < len(a); i++ {
        if pred(a[i]) {
            a[k] = a[i]
            k++
        }
    }
    return k
}