# 2.8 In-Place Modification

In-place modification changes an array without allocating another array of the same size. The goal is to reuse the input storage while preserving the part of the data that has not yet been read. This pattern is common in filtering, deduplication, partitioning, reversing, rotation, merging, and compaction.

## Problem

Given an array `a`, transform it using only `O(1)` extra space.

For example, remove all zero values:

```text
[0, 3, 0, 4, 5, 0, 6]
```

and return:

```text
[3, 4, 5, 6]
```

The result can occupy the front of the same array. The unused tail may contain old values and should usually be ignored.

## Solution: Read and Write Pointers

Use one pointer to scan the input and one pointer to mark the next output position.

```go
func RemoveZeros(a []int) []int {
	write := 0

	for read := 0; read < len(a); read++ {
		if a[read] != 0 {
			a[write] = a[read]
			write++
		}
	}

	return a[:write]
}
```

The returned slice is the meaningful part of the array. The backing array may still contain old values after `write`.

## Invariant

Before each iteration:

```text
a[0:write] contains exactly the nonzero values from a[0:read], in the same order
a[read:] has not yet been inspected
```

When `a[read]` is zero, the algorithm does not write anything. When `a[read]` is nonzero, the value is copied to `a[write]`, and `write` advances.

The assignment is safe because `write <= read`. Therefore the algorithm never overwrites an unread element.

## Example

Input:

```text
[0, 3, 0, 4, 5, 0, 6]
```

Progress:

| read | value | write before | action  | prefix after |
| ---: | ----: | -----------: | ------- | ------------ |
|    0 |     0 |            0 | skip    | []           |
|    1 |     3 |            0 | write 3 | [3]          |
|    2 |     0 |            1 | skip    | [3]          |
|    3 |     4 |            1 | write 4 | [3, 4]       |
|    4 |     5 |            2 | write 5 | [3, 4, 5]    |
|    5 |     0 |            3 | skip    | [3, 4, 5]    |
|    6 |     6 |            3 | write 6 | [3, 4, 5, 6] |

Final result:

```text
[3, 4, 5, 6]
```

## Replace Values In Place

Some modifications keep the same length. In that case one pointer is enough.

```go
func ReplaceNegativeWithZero(a []int) {
	for i := 0; i < len(a); i++ {
		if a[i] < 0 {
			a[i] = 0
		}
	}
}
```

Invariant:

```text
Before iteration i, all elements in a[0:i] have already been normalized.
```

This is safe because each element is read before it is overwritten, and later iterations do not need the old value.

## Remove Elements In Place

A general filter can be written as follows.

```go
func FilterInPlace(a []int, keep func(int) bool) []int {
	write := 0

	for read := 0; read < len(a); read++ {
		if keep(a[read]) {
			a[write] = a[read]
			write++
		}
	}

	return a[:write]
}
```

Example:

```go
a := []int{7, 2, 9, 1, 5, 3}

a = FilterInPlace(a, func(x int) bool {
	return x < 5
})

// a is [2, 1, 3]
```

This version is stable for kept elements, since accepted values are written in the same order they are read.

## Deduplicate a Sorted Array

If equal values are adjacent, in-place deduplication uses the same read/write pattern.

```go
func UniqueSorted(a []int) []int {
	if len(a) == 0 {
		return a
	}

	write := 1

	for read := 1; read < len(a); read++ {
		if a[read] != a[write-1] {
			a[write] = a[read]
			write++
		}
	}

	return a[:write]
}
```

Invariant:

```text
a[0:write] contains the unique values from a[0:read], in sorted order
```

The sorted precondition matters. Without it, duplicate values may be separated, so comparing with `a[write-1]` would miss duplicates.

## Transform While Preserving Length

When every input element produces exactly one output element, modify directly.

```go
func SquareInPlace(a []int) {
	for i := range a {
		a[i] = a[i] * a[i]
	}
}
```

This is safe when the new value at `a[i]` does not affect future reads.

If future computations depend on the original array, copy first or store enough old state before overwriting.

## Reverse In Place

Reversal swaps symmetric positions.

```go
func Reverse(a []int) {
	l := 0
	r := len(a) - 1

	for l < r {
		a[l], a[r] = a[r], a[l]
		l++
		r--
	}
}
```

Invariant:

```text
Before each iteration, all positions outside [l, r] have already been placed in their final reversed positions.
```

The middle element of an odd-length array needs no action.

## Move Zeros to the End

This variant preserves the order of nonzero elements and fills the remaining positions with zero.

```go
func MoveZerosToEnd(a []int) {
	write := 0

	for read := 0; read < len(a); read++ {
		if a[read] != 0 {
			a[write] = a[read]
			write++
		}
	}

	for write < len(a) {
		a[write] = 0
		write++
	}
}
```

The first pass compacts nonzero values. The second pass cleans the tail.

Without the second pass, the tail would contain stale values from the original array.

## Merge Into Existing Buffer

Some in-place algorithms write from the end to avoid overwriting unread values.

Suppose `a` has enough capacity to hold both sorted arrays, and the first `m` positions contain valid data. Array `b` has length `n`.

```go
func MergeSortedInto(a []int, m int, b []int) {
	i := m - 1
	j := len(b) - 1
	write := m + len(b) - 1

	for j >= 0 {
		if i >= 0 && a[i] > b[j] {
			a[write] = a[i]
			i--
		} else {
			a[write] = b[j]
			j--
		}
		write--
	}
}
```

This writes from right to left. It is safe because the largest remaining value is placed into the last available position, and no unread value in `a[0:m]` is overwritten.

## Complexity

Most in-place linear transformations have:

```text
Time:  O(n)
Space: O(1)
```

The output may be shorter than the input. In that case, the algorithm returns the new logical length or a sliced view.

## Common Pitfalls

Returning the original array after compaction exposes stale tail values. Return `a[:write]`.

Writing ahead of the read pointer can overwrite unread input. Check that `write <= read`, or write from the opposite end.

Forgetting to clean the tail causes incorrect results when the full array is later inspected.

Using in-place modification when callers expect the original array to remain unchanged creates aliasing bugs.

Deduplicating with the sorted-array method on unsorted input gives incomplete results.

## Takeaway

In-place modification is safe when the algorithm separates read positions, write positions, and unprocessed data. The most common pattern is a read pointer that scans every element and a write pointer that builds the output prefix. State the invariant before writing the loop; it prevents most overwrite and boundary bugs.