Auxiliary Space & In-Place

## Two different measures Space complexity can be quoted two ways, and the two differ by exactly one term: - **Total space** — every cell of memory the algorithm occupies while running, *including the input it was handed*. - **Auxiliary space** — only what the algorithm allocates *beyond* that input. Because the input is a fixed cost that every solution to the same problem pays, total space is a poor way to compare solutions. Two candidates for the same task, one keeping a single running counter and one building a full copy of the data, would both be reported as O(n) total — which hides the entire difference between them. Auxiliary space separates them: O(1) versus O(n). That is why "what is your space complexity?" in an interview is, by default, a question about auxiliary space. ## What counts as auxiliary Anything the algorithm brings into existence: | What you allocate | Typical auxiliary cost | | --- | --- | | A handful of indices, counters, accumulators | O(1) | | A visited/seen set over the elements processed | O(n) | | A frequency map over distinct keys observed | O(k), k = distinct keys | | A one-dimensional table over positions | O(n) | | A two-dimensional table over two sequences | O(n·m) | | A temporary buffer merged back into the input | O(n) | | Recursive call frames | O(depth) | Two entries there are worth dwelling on. First, a frequency map is **not** automatically O(n): its size is bounded by the number of *distinct* keys, so counting how often each of 26 letters appears in a billion-character stream is O(1) auxiliary, while counting distinct session identifiers in the same stream is O(n) in the worst case. Quoting O(n) for both is a common sloppiness. Second, the call stack is real memory: a recursive routine that allocates nothing on the heap still spends one frame per level of depth, and that belongs in the space figure. ## The output question The honest ambiguity is whether the answer you must return counts. If the problem says "return a new array of n running averages", no solution can use less than O(n) for the result — so counting it makes the measure useless again, exactly as counting the input did. The common convention is therefore to *exclude the required output* and report the working memory beyond it. But conventions differ between textbooks, courses and interviewers, so the safe move is one clause: "O(1) auxiliary beyond the output array, which is itself O(n)." That sentence is correct under every convention and shows you know the distinction exists. An interviewer who wanted the other convention will simply agree. A related trap: a routine that *builds nothing* but returns a view, slice or index range into the input has not spent O(n) — it spent O(1). Whether your language of thought copies or aliases here matters, and interviewers do probe it. ## How to say it A complete answer names both numbers when they differ meaningfully: > "One pass, two accumulators, no allocation — O(1) auxiliary space, O(n) total counting the input." > "I keep a set of the identifiers seen so far, so O(n) auxiliary in the worst case where every row is distinct, and O(1) when the identifier alphabet is small." Note how the second answer states what the O(n) is a function of. "O(n) space" with no statement of what n counts is where most junior answers lose points, because the same routine can be O(1) or O(n) depending on whether n means rows read or distinct keys retained. ## Wrong turns to avoid - **"Reading the input costs space."** Reading costs time. The input already exists; you did not allocate it. - **"I only allocated one map, so it's O(1)."** The number of *objects* you create is irrelevant; the number of *cells* they hold is the measure. One map can be the biggest thing in the process. - **"Space is whatever is left after the function returns."** No — it is the peak occupancy during the run. A buffer that is discarded at the end still had to fit in memory while it existed. - **"Auxiliary means heap only."** Stack frames are memory on the same budget.