What Is an In-Place Algorithm? Why O(1) Space Claims Are Tricky

You've solved the problem. Your code works. Then the interviewer says: "Can you do it in-place?"

If your first instinct is to create a new array and copy elements over, congratulations. You've just found the correct answer to the wrong problem. Here's exactly what an in-place algorithm means, why the definition is fuzzier than textbooks let on, and how to recognize when an interviewer is asking for it.

What an In-Place Algorithm Actually Does

An in-place algorithm transforms its input without allocating memory proportional to the input size. The original data structure is modified directly. Only a constant amount of extra memory is used.

The classic contrast: reversing an array by allocating a second array of the same size is out-of-place. Reversing it by swapping elements from both ends with a couple of index variables is in-place.

That distinction sounds clean until you run into the recursion problem.

Array Reversal Is the Hello World. Here's Why.

Two pointers, one from each end, swap and advance until they meet.

def reverse(nums: list[int]) -> None:
    left, right = 0, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

function reverse(nums: number[]): void {
    let left = 0;
    let right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
}

Two integer variables. That's it. O(1) extra space regardless of input length.

Notice the return type is None / void. In-place algorithms modify their input. If a function returns a brand-new collection, it's almost certainly not in-place.

O(1) Space, With One Giant Asterisk

The strict definition of in-place is O(1) extra space. Quicksort is universally described as in-place. Quicksort's recursive implementation uses O(log n) stack space. That's not O(1). The computer science community has collectively decided to let this one slide.

The working definition in interviews and most of the literature: in-place means no auxiliary data structure proportional to n. A small recursion stack (O(log n)) is tolerated. An extra array of size n is not.

The real dividing line is whether you're allocating O(n) extra space on the heap. Stack frames from recursion, a fixed number of variables, a constant-size lookup table: those don't count.

Merge sort fails this test. The merge step needs a temporary array of size O(n). That allocation disqualifies it, even though merge sort is faster and more stable than quicksort in practice.

Algorithm	In-Place?	Extra Space	Notes
Array reversal	Yes	O(1)	Classic two-pointer
Quicksort	Yes	O(log n)	Recursion stack
Heapsort	Yes	O(1)	Iterative heap ops
Bubble / insertion sort	Yes	O(1)	Nested loops, no aux array
Merge sort	No	O(n)	Merge step allocates
Counting sort	No	O(k)	Frequency array
Hash map deduplication	No	O(n)	Extra structure

The pattern: in-place sorting algorithms that partition or shift elements qualify. Sorting algorithms that need auxiliary arrays for their core operation do not.

The Gotchas Interviewers Actually Test

Swapping is free, but copying is not. When you swap two elements, you need at most one temporary variable. When you copy elements into a new array, you've allocated O(n). This trips up people who think "I'm not using much extra memory" without actually counting their allocations. Your interviewer is counting.

Recursive in-place solutions still use stack space. Quicksort with recursion is called in-place, but if you implement an "in-place reversal" recursively, your stack depth grows with the input. Technically not O(1). If an interviewer pushes back, reach for the iterative version.

The input is being modified. Always confirm whether destroying the original array is acceptable. In an interview it usually is, but asking the question signals that you think about side effects, which is exactly the kind of thing interviewers write down.

"In-place" says nothing about time complexity. You can have an O(n²) in-place algorithm (insertion sort) and an O(n log n) out-of-place one (merge sort). Time and space are independent axes.

The Four Patterns You'll See Over and Over

Two pointers. One from each end, or slow and fast through the array. No auxiliary array needed. Remove Duplicates from Sorted Array, Move Zeroes, and Container With Most Water are all two-pointer, all in-place. See the two pointer algorithm guide for the full breakdown.

Partition / Dutch National Flag. Rearrange elements around a pivot or value category using swaps. Three logical buckets, one pass, O(1) space. This is LeetCode 75 (Sort Colors) verbatim:

def sort_colors(nums: list[int]) -> None:
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Three pointers, no allocation, one pass. The Dutch National Flag problem is the canonical version.

Reversal trick for rotation. Rotate an array of n elements by k positions: reverse the full array, reverse the first k elements, reverse the remaining n-k. Three in-place reversals, O(1) space, and it feels like magic until you trace through an example.

Cyclic sort. When array elements are in the range [1, n], each element belongs at a specific index. Cycle through misplaced elements and swap them home. No auxiliary array, just swaps. This is the foundation for "find the missing number" and "find the duplicate" variants.

Once you recognize these four shapes, most in-place problems are just one of them in disguise.

The Constraint Is Usually a Hint

The in-place constraint is one of the cleanest ways to distinguish engineers who think about memory from those who don't.

On embedded systems, in tight memory environments, or over very large datasets, avoiding O(n) allocations matters. Allocating a second array every time you process data puts pressure on the garbage collector and increases memory bandwidth.

More importantly: in-place problems usually have an elegant O(1)-space solution hiding behind an obvious O(n)-space one. The constraint is the interviewer's way of saying "yes, I know you can jam everything into a hash map, but can you do something interesting?" It's easy to solve "find the duplicate" by dumping everything into a hash set. Solving it in O(1) space requires noticing that the array itself can be used as a data structure (see Floyd's cycle detection).

When you hear "in-place," stop and ask: what structure already exists in this input that I can exploit?

This Is Really About Memory Tradeoffs

Understanding in-place algorithms is really understanding space complexity. The extra space your algorithm uses is what counts: auxiliary arrays, hash maps, recursion stack depth, any heap allocation that grows with input size.

The historical arc of caring about memory efficiency.

The time-space tradeoff runs in both directions. Hash maps give you O(1) lookup at the cost of O(n) space. Two pointers give you O(1) space at the cost of sometimes requiring sorted input or a specific structure. Neither is universally better. The constraint tells you which axis matters for the problem at hand.

SpaceComplexity runs voice-based mock interviews where you practice explaining your space usage out loud, not just writing code that happens to work. The gap between "my solution uses O(1) space" and being able to justify that claim to a skeptical interviewer is larger than most people expect.

Further Reading

• In-place algorithm, Wikipedia
• Introduction to Algorithms (CLRS), Chapter 7, Quicksort
• Quicksort, Wikipedia
• Dutch national flag problem, Wikipedia
• std::sort, cppreference