Hash Map Memory Optimization: When and How to Reduce Space

Your hash map solution works. Then you see: Memory Limit Exceeded.

You need to reduce space usage. But how, without breaking your solution?

This guide shows you 4 techniques to optimize hash map memory.

When Hash Map Space Is Too Much

The problem

Hash maps use O(n) space. Sometimes that's too much:

• Problem requires O(1) space
• Dataset is huge (millions of elements)
• Memory limit is strict

The question

"Can you reduce space usage?"

Technique 1: Use Set Instead of Map

When applicable

You're storing boolean values or don't need values.

Example

❌ Before (hash map):

seen = {}
for num in nums:
    if num in seen:
        return True
    seen[num] = True  # Don't need value!

✅ After (set):

seen = set()
for num in nums:
    if num in seen:
        return True
    seen.add(num)

Space saved: Set is more memory efficient than dict.

Technique 2: Sliding Window to Limit Map Size

When applicable

"Within distance k" problems.

Example: Contains Duplicate II

❌ Before (unbounded map):

def containsNearbyDuplicate(nums, k):
    index_map = {}
    for i, num in enumerate(nums):
        if num in index_map and i - index_map[num] <= k:
            return True
        index_map[num] = i
    return False
# Space: O(n)

✅ After (sliding window):

def containsNearbyDuplicate(nums, k):
    window = set()
    for i, num in enumerate(nums):
        if num in window:
            return True
        window.add(num)
        if len(window) > k:
            window.remove(nums[i - k])
    return False
# Space: O(min(n, k))

Space saved: O(n) → O(k)

Technique 3: In-Place Marking (Array Only)

When applicable

Array values are in range [1, n], can modify input.

Example: Find Duplicates

❌ Before (hash set):

def findDuplicates(nums):
    seen = set()
    result = []
    for num in nums:
        if num in seen:
            result.append(num)
        seen.add(num)
    return result
# Space: O(n)

✅ After (in-place):

def findDuplicates(nums):
    result = []
    for num in nums:
        index = abs(num) - 1
        if nums[index] < 0:
            result.append(abs(num))
        else:
            nums[index] = -nums[index]
    return result
# Space: O(1)

Space saved: O(n) → O(1)

Trade-off: Modifies input array.

Technique 4: Bit Manipulation for Boolean Flags

When applicable

Tracking boolean states for small range.

Example: Single Number

❌ Before (hash set):

def singleNumber(nums):
    seen = set()
    for num in nums:
        if num in seen:
            seen.remove(num)
        else:
            seen.add(num)
    return seen.pop()
# Space: O(n)

✅ After (XOR):

def singleNumber(nums):
    result = 0
    for num in nums:
        result ^= num
    return result
# Space: O(1)

Space saved: O(n) → O(1)

Trade-Offs

When to Optimize

Don't optimize if:

• Problem doesn't mention space constraints
• O(n) space is acceptable
• Optimization complicates code significantly

Do optimize if:

• Problem explicitly requires O(1) space
• Memory limit exceeded
• Interviewer asks "Can you reduce space?"

Summary

4 techniques to reduce hash map space:

1. Use set instead of map
2. Sliding window to limit size
3. In-place marking (array only)
4. Bit manipulation (specific problems)

The rule: Only optimize when necessary. Start with clear solution, optimize if asked.

Next steps:

• Learn when NOT to use hash maps
• Study the complete hash map guide

Optimize space when needed, not by default.