"Can You Do It in O(1) Space?" How to Answer the Space Follow-Up in a Coding Interview
Your hash map solution works. You traced an example, stated O(n) time and O(n) space, and the interviewer looks pleased. Then they ask: "Can you do it in constant space?"
For a lot of candidates, this is where the round wobbles. The first solution felt complete, and now it seems to be on trial. You start hunting for some clever trick you may never have seen.
The good news is that most constant-space follow-ups are built from a small set of moves. If you know those moves and have a calm way to talk through them, the question stops being a trap and becomes another chance to show how you think.
What the interviewer is really checking
The O(1) space question is rarely about the final answer alone. It checks a few things:
- Do you know where your memory goes? You should be able to point at the exact structure that costs O(n): the hash set, the copied array, the recursion stack.
- Can you use the input itself? Many constant-space solutions reuse the array you were given, its order, its value range, or its indices.
- Do you understand the trade-off? Saving space often costs time, readability, or the ability to keep the input unchanged.
- Can you stay organized when the goalposts move? A structured response reads as experience. A long silence followed by guessing does not.
Step 1: Name the memory you are spending
Before you search for a new idea, say out loud what is using space right now.
"Right now the extra space is the hash set of seen values, which can grow to n. The output is separate. So the question is whether I can get the same 'have I seen this?' information without storing it."
That sentence does three things. It shows you understand your own solution. It narrows the problem to one specific structure. And it gives you a clear question to work on, instead of a vague "be smarter."
Also confirm the rules, because they change the answer:
- Does the output count? Usually it does not. Returning a new array of size n can still be "O(1) extra space."
- Can I modify the input? Many in-place tricks depend on this. Ask before you use it.
- Does recursion count? A recursive DFS uses stack space. Interviewers often count it.
Step 2: Run through the five common moves
Most O(1) space solutions in interviews come from one of these patterns. Go through them quickly, out loud, and see which fits.
1. Two pointers instead of a lookup
If the input is sorted, or you can sort it, a pair of pointers often replaces a hash map. Pair sums, removing duplicates, and merging are classic examples. The trade-off: sorting costs O(n log n) time and may change the input.
2. Use the input as your memory
When values fall in a known range, like 1 to n, you can mark "seen" by flipping the sign of the value at an index, or by swapping each number into its "home" position. This shows up in finding missing or duplicate numbers. The trade-off: you are changing the input, so ask first, and mention you can restore it afterward.
3. Overwrite as you go
Problems like "remove elements" or "move zeros" can keep a write pointer and overwrite the array in place, instead of building a new one. The idea is that you never need to read a slot after you have written to it.
4. Keep a running state, not a history
Sometimes you stored a whole list when you only needed a few numbers: a running max, a previous value, two rolling variables in a dynamic programming table. If each step only looks back one or two positions, the full table can shrink to a couple of variables.
5. Bit and math tricks
XOR to find the single unpaired number, sum formulas to find a missing value, slow and fast pointers to detect a cycle. These are worth knowing, but they are the least general. If one fits, great. If you are not sure, do not force it.
A useful script:
"Let me check the usual options. It is not sorted, but sorting would let me use two pointers. Values are 1 to n, so I could also mark indices in place. Running state does not fit because I need to remember arbitrary earlier values."
Even if you are still thinking, that is a strong answer. The interviewer can see your search, and they often nudge you toward the right branch.
Step 3: State the trade-off before you code
Once you have a candidate approach, say what it costs before writing it.
"If I sort first, I get O(1) extra space, but time goes to O(n log n) and I lose the original order. If order matters for the output, that is a problem. The index-marking approach keeps O(n) time but mutates the input. Which constraint matters more here?"
This turns the follow-up into a conversation instead of a test. It also protects you from spending ten minutes coding an answer that breaks a rule nobody mentioned.
Interviewers like hearing a clear recommendation, too:
"If I can modify the input, I would go with index marking. It keeps linear time."
Step 4: Code the change, not a new solution
You rarely need to start from a blank pad. Keep your working solution visible and change only the part that used memory.
- Replace the hash set lookup with the in-place check.
- Keep variable names and structure similar so the interviewer can follow the diff.
- Trace the same example you used before. It is the fastest way to show the new version is equivalent.
Pay extra attention to edge cases that in-place tricks tend to break: duplicates, zero or negative values when you are flipping signs, and arrays of length zero or one.
When the honest answer is "not cleanly"
Sometimes O(1) space is not realistic, or the only way to get there is far slower. It is fine to say so, with reasons.
"I can get to O(1) space by comparing every pair, but that is O(n squared). For large inputs I would keep the O(n) space version. If memory were truly the bottleneck, I would look at sorting in place first."
That is not a failure. It shows you can judge a trade-off, which is what engineers do every day. Saying "I don't know" and stopping is the weak answer. Laying out the options and picking one is the strong one.
Common mistakes
- Dropping the working solution in a panic. Keep it. It is your fallback and your reference.
- Forgetting the recursion stack. A recursive solution with "no extra data structures" is still O(depth) space.
- Mutating the input without asking. Always check, and mention how you would restore it.
- Going quiet while searching. Narrate the patterns you are ruling in or out.
- Claiming O(1) space while building a new output array without saying so. Clarify whether output counts.
How to practice this
Pick five problems you already solved with a hash map or extra array. For each one, practice the full follow-up out loud in under five minutes:
- Name the structure that uses memory.
- Run through the five moves.
- State the trade-off.
- Sketch the in-place change and trace one example.
Do this with a timer and with someone, or something, asking the follow-up at a moment you do not expect. The surprise matters more than the problem. A focused practice partner in a Chrome side panel, like Luna Interview at https://lunainterview.xyz/, can help you rehearse that rhythm of being pushed on a solution and talking through the change calmly.
FAQ
Does the output array count toward space complexity? Usually not. Most interviewers mean extra space beyond the input and output. Ask to be sure.
Is modifying the input considered cheating the space rule? No, but it is a trade-off. Ask whether it is allowed, and mention you could restore the input afterward if needed.
Does recursion count as extra space? Yes. The call stack grows with recursion depth, so a recursive solution is O(depth) space unless you convert it to iteration.
What if I cannot find a constant-space solution? Explain where the memory goes, list the options you considered and why they do not fit, and propose the best trade-off you can. That is a solid answer.
Rehearse with an AI interview copilot, then browse commonly reported interview questions.