Does mutating the caller's buffer make an algorithm in-place, or is more required?

## The definition, stated precisely An algorithm is **in-place** when its auxiliary space is O(1): a fixed number of scalars — loop indices, a swap temporary, a running accumulator — whose count does not grow with the input. The widely accepted relaxation is O(log n), allowing the call stack of a divide-and-conquer routine that recurses to logarithmic depth. Anything beyond that (a scratch array proportional to n, a map keyed by the elements, a queue holding a level of a structure) disqualifies the claim. Two things the definition does **not** say: - It does not say *zero* memory. Every algorithm needs somewhere to hold a comparison result and an index. "In-place means it uses no extra memory" is the single most common wrong answer here, and the follow-up that exposes it is simply "where do you put the element while you swap two of them?" - It does not say *mutates the input*. That is a separate property — destructiveness — and it is a property of the API contract, not of the memory bound. ## Mutation and allocation are independent axes | | Allocates O(1) | Allocates O(n) | | --- | --- | --- | | **Leaves input intact** | in-place, non-destructive: scanning for a maximum, or a two-index walk that only reads | not in-place: building a transformed copy | | **Overwrites input** | in-place, destructive: swap-based reordering of the caller's buffer | not in-place, destructive: fill a scratch array, copy it back | The bottom-right cell is the one candidates misclassify. Consider a routine that rescales a caller's measurement buffer so the values sum to one: sum the buffer, allocate a same-size scratch array, write each scaled value into it, then copy the scratch back over the caller's buffer. The caller observes their data changed, so it *feels* in-place — but peak auxiliary usage was n cells. On a buffer that occupies most of available memory, that hidden doubling is precisely the failure the in-place question is asking about. The fix in that example is trivial (write the scaled value straight back into the buffer during the second pass, since each output depends only on its own input cell and the already-computed sum), and noticing that the scratch was never needed is the point of the exercise. ## Why interviewers ask "can you do it in O(1) space?" Because it forces a different solution shape. Once you cannot allocate a table keyed by the data, you must either exploit structure already present (ordering, a bounded value range, spare capacity in the existing cells) or accept more time. That is a real tradeoff, not a puzzle: the constant-space version is frequently slower, less readable, or destroys information the caller may still need. A good answer states the price rather than presenting the constant-space version as strictly better. ## The API designer's chair If you are the one shipping the routine, in-place is a contract decision, and it has consequences beyond the memory number: - **Destructiveness must be visible in the name and the documentation.** A caller who wanted to keep the original and did not read carefully will lose it, and the bug surfaces far from your routine. - **Retries and comparisons become impossible.** A caller who wants to re-run with different parameters, or diff the result against the original, now has to copy defensively first — and if every caller copies, your in-place routine has *increased* total memory use across the system while looking cheaper in isolation. - **Aliasing gets sharp.** If two names refer to the same buffer, or one region overlaps another, an in-place routine can read a cell it has already overwritten. Non-destructive versions are immune by construction. - **Offering both is often right.** A destructive core plus a thin non-destructive wrapper that copies once gives callers the choice, at the cost of one more name to document. The rule of thumb: reach for in-place when the data is large relative to the memory budget, when the caller genuinely has no further use for the original, or when the allocation itself is the bottleneck. Otherwise the copy is cheap insurance, and an interviewer who hears you weigh it that way is hearing production judgment rather than a memorized definition. ## Sound bites that pass, and ones that fail Passes: "In-place means O(1) auxiliary — indices and a swap temporary. I'm also overwriting the caller's buffer, which the contract has to say." Fails: "It's in-place because I didn't create a new array" (said about a routine holding a full-size map); "in-place uses no memory"; "in-place just means it modifies the argument".