Dynamic Arrays

Dynamic arrays are the default when you need random access and efficient appends. For interviews, the important distinction is between logical length, allocated capacity, and the cost of shifting or copying data.

1. Separate Per-operation and Amortized Costs

Operation on n elements	Time	Reason
Read or replace at a valid index	$O(1)$	Direct indexing
Append	$O(1)$ amortized, $O(n)$ worst case	Occasionally allocate and copy
Remove last item	$O(1)$ without shrinking	No remaining items shift
Insert or erase at index i	$O(n-i)$ shifting	Preserve the order of the suffix
Find an arbitrary value	$O(n)$	No search index or sorted-order guarantee
Copy or slice k elements	$O(k)$ when copied	Output allocation and copying

If a container grows by a fixed factor greater than one, n appends perform $O(n)$ total copying. With doubling, copied capacities form 1+2+4+..., a geometric sum below a constant multiple of n. Growing by one slot instead copies 1+2+...+(n-1), giving $O(n^2)$ total work. Amortized cost is a bound over an operation sequence, not a promise that each append is fast.

2. Maintain Length and Capacity Correctly

In a custom array, 0 <= size <= capacity; only positions [0,size) contain logical elements. Validate against size, not capacity. On append, grow before writing when full; copy only the live prefix, write at size, then increment size. If initial capacity may be zero, use a positive minimum when growing. See Design Dynamic Array.

If removing an item leaves a reference in unused storage, clear it when the language's memory model requires this to release the object. A maintained size alone does not necessarily release references from a backing array.

Automatic shrinking needs a gap between thresholds. Growing when full and halving immediately at half-full can thrash under alternating insertions and deletions. Halve capacity at quarter-full instead, with a fixed minimum capacity: after shrinking, the array is half-full and has room before its next growth. Occasional shrink copies make deletion amortized $O(1)$ rather than worst-case $O(1)$.

3. Avoid Repeated Shifts and Accidental Aliasing

To remove all unwanted values while preserving order, do not repeatedly erase from the middle. Use a reader to scan and a writer to compact retained values into a prefix, then resize once if needed. Each value is read once, so the scan is $O(n)$ with $O(1)$ auxiliary space. Remove Element uses this pattern.

If order does not matter, deleting a known index can swap in the last value and pop the tail, avoiding the suffix shift. For repeated front removals, use a queue or deque; for frequent membership checks, add a set or map.

Know whether a slice is a copy or a view. Python list slices copy references into a new list; nested objects are still shared. Go slices can share the backing array, and an append may keep that array or allocate a new one depending on capacity. A reference to a small view may also keep a large backing allocation alive. Clarify whether a requested copy is shallow or independent at every level.

When final output size is known, preallocate where the language allows it. This can reduce allocation overhead but does not remove the $O(n)$ cost of writing n outputs; Concatenation of Array is a simple application.

4. Key Takeaways

• size controls valid indices; spare capacity is not part of the logical array.
• Geometric growth gives linear total copying across appends, while one append can still cost $O(n)$.
• Compact many deletions with a writer instead of shifting the suffix repeatedly.
• “In place” does not describe slice aliasing or library allocation costs. State input mutation and auxiliary memory separately.

Continue to Two Pointers for compaction and in-place partitioning, String Manipulation for building immutable outputs efficiently, and Linked Lists when the task is primarily local node rewiring.