# Array Compaction

# 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.

```id="array-compaction"
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

```python id="array-compaction-python"
def compact(a, predicate):
    k = 0
    for i in range(len(a)):
        if predicate(a[i]):
            a[k] = a[i]
            k += 1
    return k
```

```go id="array-compaction-go"
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
}
```