Should a growable array's capacity ever shrink automatically in a service whose catalog peaks each December?

## The question behind the question This is not really about a data structure. It is about whether a memory footprint you can see is a memory cost you should pay engineering attention to, and who maintains the answer after you have moved on. That framing is what separates a good answer here from a technically correct one. ## Three policies **Never shrink.** Capacity is a high-water mark; the block is released only when the structure itself dies. Erase stays cheap and predictable — no allocation, no copy, no invalidation — and a structure that cycles between fill and drain does its allocation work exactly once. This is the default in most growable-array designs, and it is the right default. **Shrink on explicit request.** The owner decides, at a moment it chooses, to pay an O(n) copy into a right-sized block. All the cost is visible at the call site, and the code that owns the structure is the code that knows whether anyone is holding a position into it. **Shrink automatically on erase.** The structure watches its own occupancy and reallocates downward when it drops below a threshold. Convenient, and the source of the trap below. ## Why symmetric thresholds thrash The naive automatic rule is "when the array is half empty, halve the capacity". Consider the boundary: the structure has just shrunk, so it is now full. One append overflows and reallocates upward. One erase drops it back to half and reallocates downward. Alternate append and erase and *every single operation* pays a full O(n) copy — the amortized guarantee that makes growable arrays worth using is destroyed by an adversarial or merely unlucky access pattern. The fix is hysteresis: separate the shrink trigger from the shrink target. Shrink when the size falls to roughly a quarter of capacity, and shrink to about half of capacity. After a shrink the structure is half full, so it takes a linear number of appends to trigger a growth or a linear number of erases to trigger the next shrink. The gap between the two thresholds is what preserves the amortized bound. If you remember one technical fact from this topic, make it this one — the reasoning generalises to every occupancy-driven resize policy you will ever design. ## What shrinking costs beyond time Shrinking has the *same* consequences as growing, which surprises people who think of it as pure reclamation: - It is O(n): allocate, copy the survivors, release the old block. - It briefly *raises* peak memory, because both blocks are live during the copy. A memory-pressure-triggered shrink can therefore push you over the edge it was meant to pull you back from. - It relocates every element, so anything holding a position into the old block is invalidated exactly as it would be by growth. ## The seasonal case, concretely A catalog that is huge in December and tiny in February is the textbook motivating example, and the honest answer usually is: pay the peak, unless you have a number that says otherwise. Gather it — resident memory of a long-idled instance against a freshly started instance loaded with the same February data. The delta is exactly what any shrink policy is worth. Then weigh it against three things people forget: 1. **You will need the capacity again.** Next December it grows back, and you pay the growth copies you avoided by not shrinking. Shrinking the trough only wins if the trough is long relative to the cycle. 2. **Releasing is not returning.** Freeing a block hands it to the allocator. Whether the operating system ever gets those pages back depends on the allocator, block size and fragmentation. The graph you are trying to move may not move. 3. **Someone maintains the policy.** A hand-tuned occupancy rule is a permanent piece of subtle code that a future reader must reason about. A scheduled rebuild at a known quiet moment — construct a fresh structure sized to the survivors, swap it in, drop the old one — is boring, obvious in review, and happens where no one holds a position into the storage. For a seasonal workload with a known calendar, boring wins. ## Ecosystems disagree, which proves it is a policy Growable arrays in C++ and Rust never hand capacity back on their own; reducing the block is an explicit, and in one case non-binding, request. The list type in mainstream Python builds does reallocate downward once the size falls well below the allocated slots. Two reasonable communities, opposite defaults, same structure. That is the tell that this is a policy question with no universally correct answer — which is precisely why an interviewer asks it at this level and why "the runtime handles it" is not an answer, it is an assumption to go and check. ## Answering the skeptic Bring three things: the measured delta, the cost of the alternative, and the failure mode of doing it automatically. "Idle instances hold 340 MB more than they need, times 40 instances, for four months. An automatic shrink risks thrash and invalidates positions. A rebuild at the January boundary costs one linear copy at 3 a.m. and no ongoing complexity." That is a decision, with a number and an owner, and it is what the level is testing.