Space Optimization Techniques in DSA

In interviews, an O(n) space solution is often just the starting point. Interviewers love follow-ups like “Can you do it in O(1) space?” This post covers six techniques that let you slash space complexity without sacrificing time.

---

1. Rolling Array for DP — From 2D to 1D

Many DP problems fill a 2D table where each row only depends on the previous row. Instead of storing the entire table, keep just two rows (or even one).

Example: Unique Paths (LeetCode 62)

Naive DP: O(m * n) time and space.

def unique_paths_2d(m, n):
    """
    Count paths from top-left to bottom-right in an m x n grid.
    Only move right or down.

    dp[i][j] = dp[i-1][j] + dp[i][j-1]

    Time: O(m * n), Space: O(m * n)
    """
    dp = [[1] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[m - 1][n - 1]

Optimized: Each row only needs the previous row. Use a single 1D array.

def unique_paths_1d(m, n):
    """
    Same problem, but only keep one row.

    dp[j] already holds the "above" value from the previous row.
    dp[j-1] holds the "left" value from the current row.
    So dp[j] += dp[j-1] works in-place.

    Time: O(m * n), Space: O(n)
    """
    dp = [1] * n

    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]

    return dp[n - 1]

Example: 0/1 Knapsack

The classic knapsack uses dp[i][w] — item i, capacity w. Since each row depends only on the previous row, we can use a single array. The trick: iterate capacity in reverse to avoid using updated values.

def knapsack_optimized(weights, values, capacity):
    """
    0/1 Knapsack with O(capacity) space.

    Key: iterate w from capacity down to weights[i].
    This ensures dp[w - weights[i]] is from the previous "row."

    Time: O(n * capacity), Space: O(capacity)
    """
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        # Reverse order to avoid counting item i twice
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[capacity]

Why Reverse Order?

If we iterate w forward, dp[w - weights[i]] may already include item i (from this iteration), effectively allowing unlimited copies. Reverse order ensures we read “old” values.

# Forward order (WRONG for 0/1 knapsack — this solves unbounded knapsack):
for w in range(weights[i], capacity + 1):
    dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

# Reverse order (CORRECT for 0/1 knapsack):
for w in range(capacity, weights[i] - 1, -1):
    dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

Example: Edit Distance (LeetCode 72)

def min_distance(word1, word2):
    """
    Edit distance with O(min(m, n)) space.

    Each cell depends on dp[i-1][j], dp[i][j-1], dp[i-1][j-1].
    Keep one row + one variable for the diagonal.

    Time: O(m * n), Space: O(min(m, n))
    """
    m, n = len(word1), len(word2)

    # Ensure word2 is shorter for less space
    if m < n:
        return min_distance(word2, word1)

    dp = list(range(n + 1))  # Base case: first row

    for i in range(1, m + 1):
        prev_diag = dp[0]    # dp[i-1][j-1]
        dp[0] = i            # Base case: first column

        for j in range(1, n + 1):
            temp = dp[j]     # Save dp[i-1][j] before overwrite
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev_diag
            else:
                dp[j] = 1 + min(
                    prev_diag,    # replace
                    dp[j],        # delete (above)
                    dp[j - 1],    # insert (left)
                )
            prev_diag = temp

    return dp[n]

Rolling Array Summary

Pattern	Before	After
Row depends on prev row only	O(m * n)	O(n)
Cell depends on left + above	Use 1 row, iterate forward	O(n)
Cell depends on above-left diagonal	Use 1 row + prev_diag variable	O(n)
0/1 choice (knapsack)	Use 1 row, iterate backward	O(n)

---

2. In-Place Algorithms

Dutch National Flag (LeetCode 75: Sort Colors)

Sort an array of 0s, 1s, and 2s in one pass with O(1) space.

def sort_colors(nums):
    """
    Dutch National Flag algorithm.

    Three pointers: lo (boundary of 0s), mid (current), hi (boundary of 2s).
    - nums[mid] == 0: swap with lo, advance both
    - nums[mid] == 1: advance mid
    - nums[mid] == 2: swap with hi, shrink hi (don't advance mid)

    Time: O(n), Space: O(1)
    """
    lo, mid, hi = 0, 0, len(nums) - 1

    while mid <= hi:
        if nums[mid] == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1
            # Don't advance mid — the swapped element needs checking

    return nums

Rotate Array (LeetCode 189)

Rotate an array right by k positions in O(1) space using the reversal trick.

def rotate(nums, k):
    """
    Rotate array right by k positions using three reversals.

    [1,2,3,4,5,6,7], k=3
    Step 1: Reverse all      → [7,6,5,4,3,2,1]
    Step 2: Reverse [0..k-1] → [5,6,7,4,3,2,1]
    Step 3: Reverse [k..n-1] → [5,6,7,1,2,3,4]

    Time: O(n), Space: O(1)
    """
    n = len(nums)
    k %= n

    def reverse(lo, hi):
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo += 1
            hi -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)

Move Zeroes (LeetCode 283)

def move_zeroes(nums):
    """
    Move all zeros to end, maintaining order of non-zeros.

    Two pointers: write_pos tracks where next non-zero goes.

    Time: O(n), Space: O(1)
    """
    write_pos = 0

    for i in range(len(nums)):
        if nums[i] != 0:
            nums[write_pos], nums[i] = nums[i], nums[write_pos]
            write_pos += 1

---

3. Bit Manipulation for Space — Using an Integer as a Set

When elements are small (say 0 to 25 for lowercase letters), you can use a single integer as a bit set instead of a hash set or boolean array.

Example: Check for Duplicate Characters

def has_all_unique_chars(s):
    """
    Check if string has all unique lowercase characters.

    Use a 26-bit integer as a set.
    Bit i is 1 if character 'a'+i has been seen.

    Time: O(n), Space: O(1) — just one integer
    """
    seen = 0

    for ch in s:
        bit = 1 << (ord(ch) - ord('a'))
        if seen & bit:
            return False
        seen |= bit

    return True

Example: Longest Substring Without Repeating Characters (Bit Set Variant)

def longest_unique_substring_bits(s):
    """
    Find longest substring with all unique characters.
    Assumes lowercase English letters only.

    Use a bitmask as a sliding window character set.

    Time: O(n), Space: O(1)
    """
    seen = 0
    left = 0
    max_len = 0

    for right in range(len(s)):
        bit = 1 << (ord(s[right]) - ord('a'))

        while seen & bit:
            # Remove left character
            seen ^= (1 << (ord(s[left]) - ord('a')))
            left += 1

        seen |= bit
        max_len = max(max_len, right - left + 1)

    return max_len

Example: Find the Single Number (LeetCode 136)

def single_number(nums):
    """
    Every element appears twice except one. Find it.

    XOR all elements. Pairs cancel out (a ^ a = 0).

    Time: O(n), Space: O(1)
    """
    result = 0
    for num in nums:
        result ^= num
    return result

Bit Set Operations

Operation	Code	Meaning
Add element x	s |= (1 {'<'}{'<'} x)	Set bit x
Remove element x	s &= ~(1 {'<'}{'<'} x)	Clear bit x
Check membership	s & (1 {'<'}{'<'} x)	Is bit x set?
Toggle element	s ^= (1 {'<'}{'<'} x)	Flip bit x
Union	a | b	OR
Intersection	a & b	AND
Size (popcount)	bin(s).count('1')	Count set bits

---

4. Morris Traversal — O(1) Space Tree Traversal

Normal in-order traversal uses O(h) space for the recursion stack (or an explicit stack). Morris traversal achieves O(1) space by temporarily modifying the tree — threading the rightmost node of the left subtree back to the current node.

def morris_inorder(root):
    """
    In-order traversal with O(1) space.

    Idea: For each node, find its in-order predecessor (rightmost
    in left subtree). Thread it back to current. When we return
    via the thread, we undo it and move right.

    Time: O(n) — each edge traversed at most twice
    Space: O(1) — no stack, no recursion
    """
    result = []
    current = root

    while current:
        if current.left is None:
            # No left subtree — visit and go right
            result.append(current.val)
            current = current.right
        else:
            # Find in-order predecessor
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if predecessor.right is None:
                # First visit — create thread
                predecessor.right = current
                current = current.left
            else:
                # Second visit — remove thread, visit node
                predecessor.right = None
                result.append(current.val)
                current = current.right

    return result

Morris Pre-Order Traversal

def morris_preorder(root):
    """
    Pre-order traversal with O(1) space.

    Same as in-order Morris, but visit the node on first encounter
    (when creating the thread) instead of the second.

    Time: O(n), Space: O(1)
    """
    result = []
    current = root

    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if predecessor.right is None:
                # First visit — visit NOW (pre-order) and create thread
                result.append(current.val)
                predecessor.right = current
                current = current.left
            else:
                # Second visit — just remove thread
                predecessor.right = None
                current = current.right

    return result

When to Use Morris Traversal

• When the interviewer asks for O(1) space tree traversal
• When you cannot modify the tree permanently (Morris restores it)
• When you need to validate BST, find kth smallest, etc., without a stack

Complexity Proof

Each node is visited at most twice (once going down, once coming back via thread). Each edge is traversed at most twice (once to create thread, once to remove it). Total: O(n) time.

---

5. Constant-Space Linked List Operations

Reverse a Linked List In-Place

def reverse_list(head):
    """
    Reverse a singly linked list in O(1) space.

    Three pointers: prev, current, next_node.

    Time: O(n), Space: O(1)
    """
    prev = None
    current = head

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

Reorder List (LeetCode 143)

Given 1 → 2 → 3 → 4 → 5, reorder to 1 → 5 → 2 → 4 → 3. Three steps, all O(1) space:

def reorder_list(head):
    """
    Reorder list: L0 → Ln → L1 → Ln-1 → L2 → ...

    Step 1: Find middle (slow/fast pointers)
    Step 2: Reverse second half
    Step 3: Merge two halves

    Time: O(n), Space: O(1)
    """
    if not head or not head.next:
        return

    # Step 1: Find middle
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse second half
    second = slow.next
    slow.next = None   # Cut the list
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    second = prev

    # Step 3: Merge
    first = head
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2

Palindrome Linked List (LeetCode 234)

def is_palindrome(head):
    """
    Check if linked list is palindrome in O(1) space.

    Find middle, reverse second half, compare, restore.

    Time: O(n), Space: O(1)
    """
    # Find middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    prev = None
    curr = slow
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    # Compare
    left, right = head, prev
    result = True
    while right:
        if left.val != right.val:
            result = False
            break
        left = left.next
        right = right.next

    return result

---

6. Floyd’s Cycle Detection — O(1) Space

Detect Cycle (LeetCode 141)

def has_cycle(head):
    """
    Detect if linked list has a cycle.

    Tortoise (slow) moves 1 step, hare (fast) moves 2 steps.
    If they meet, there's a cycle.

    Time: O(n), Space: O(1)
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

Find Cycle Start (LeetCode 142)

def detect_cycle(head):
    """
    Find the node where the cycle begins.

    After slow and fast meet inside the cycle, move one pointer
    back to head. Advance both at speed 1 — they meet at the
    cycle start.

    Time: O(n), Space: O(1)
    """
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # Move one pointer to head
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow

    return None

Find Duplicate Number (LeetCode 287)

Floyd’s algorithm works on arrays too. Treat nums[i] as a “next pointer.”

def find_duplicate(nums):
    """
    Find the duplicate in [1..n] array of n+1 elements.

    Treat the array as a linked list: index → nums[index].
    A duplicate means two indices point to the same value → cycle.

    Time: O(n), Space: O(1)
    """
    # Phase 1: Find intersection point
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Phase 2: Find cycle entrance
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

Why It Works

If the cycle has length C and the distance from head to cycle start is L:

• When they meet, slow has traveled L + k steps and fast has traveled 2(L + k) steps.
• The difference L + k is a multiple of C.
• Moving a pointer back to head and advancing both at speed 1: after L steps, both are at the cycle start.

---

Complexity Comparison

Technique	Before	After	When to Use
Rolling array	O(m * n) space	O(n) space	DP where row depends on prev row
In-place partitioning	O(n) space	O(1) space	Sorting/partitioning with few categories
Bit set	O(n) space for HashSet	O(1) space (1 integer)	Small alphabet (e.g., 26 letters)
Morris traversal	O(h) stack space	O(1) space	Tree traversal without recursion/stack
In-place linked list	O(n) extra space	O(1) space	Reversal, reordering, palindrome check
Floyd’s algorithm	O(n) for HashSet	O(1) space	Cycle detection in lists or arrays

---

Practice Problems

Problem	Platform	Difficulty	Technique
Unique Paths	LeetCode 62	Medium	Rolling array
Edit Distance	LeetCode 72	Medium	Rolling array + diagonal
Sort Colors	LeetCode 75	Medium	Dutch National Flag
Rotate Array	LeetCode 189	Medium	Three reversals
Single Number	LeetCode 136	Easy	XOR
Find the Duplicate Number	LeetCode 287	Medium	Floyd’s
Linked List Cycle II	LeetCode 142	Medium	Floyd’s
Palindrome Linked List	LeetCode 234	Easy	Reverse half
Reorder List	LeetCode 143	Medium	Split + reverse + merge
Binary Tree Inorder Traversal	LeetCode 94	Easy	Morris traversal

---

Key Takeaways

1. Rolling arrays are the single most impactful optimization in DP — always check if each row depends only on the previous row.
2. Iterate backward in 1D knapsack to prevent using the same item twice.
3. Bit manipulation as sets works when the universe is small (up to 64 elements with a 64-bit integer).
4. Morris traversal is the only way to traverse a tree in O(1) space — it temporarily modifies and then restores the tree.
5. Floyd’s algorithm is not just for linked lists — any function from a finite set to itself has a cycle, and Floyd finds it.
6. In interviews, always mention the space optimization as a follow-up even if not asked — it shows depth.