LeetCode 2502 - Design Memory Allocator

The problem requires designing a memory allocator that manages a fixed-size memory array. Initially, all memory units are free, and the allocator supports two operations: allocating a block of consecutive free memory units for a given ID (mID) and freeing all memory units…

leetcodemediumarrayhash-tabledesignsimulation

LeetCode Problem 2502

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Design, Simulation

Solution

Problem Understanding

The problem requires designing a memory allocator that manages a fixed-size memory array. Initially, all memory units are free, and the allocator supports two operations: allocating a block of consecutive free memory units for a given ID (mID) and freeing all memory units associated with a given mID. Allocation should always select the leftmost available block of the requested size. Multiple blocks can be allocated to the same mID, and freeing a memory ID should release all blocks associated with that mID.

The input consists of integer parameters: n for the memory size, size for the allocation request, and mID for identification of allocations. The output is either the starting index of the allocated block (or -1 if allocation fails) or the number of memory units freed.

Constraints (n, size, mID <= 1000 and up to 1000 operations) indicate that a straightforward simulation approach is feasible because the memory array and the number of operations are relatively small. Edge cases include trying to allocate more memory than available, freeing an mID that does not exist, and multiple allocations to the same mID.

Approaches

Brute Force

A simple brute-force solution is to maintain an array representing memory. For allocation, iterate from left to right and check for a block of consecutive zeros of length size. If found, fill it with mID and return the starting index. For freeing, iterate over the entire array, count occurrences of mID, and reset those positions to zero.

This approach works correctly because it simulates memory exactly as described. However, both allocation and freeing require scanning the entire array, making the time complexity O(n) per operation. While feasible given the constraints, it is not optimal if the memory size or operation count were larger.

Optimized Insight

A more optimal approach is to maintain a map (hash table) from mID to a list of ranges (start index and length) representing allocated blocks. Freeing becomes more efficient because you can directly access all blocks associated with a specific mID without scanning the entire memory array. However, allocation still requires scanning the array for free segments. Given the constraints (n <= 1000), a simple array simulation is sufficient, and using a map only slightly improves free operations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per operation O(n) Simulates memory array directly, scans memory for allocation and free operations
Optimized O(n) per allocation, O(k) per free O(n + k) Tracks allocated blocks per mID to speed up freeing; still scans memory for allocation

Algorithm Walkthrough

  1. Initialize a memory array of size n with all elements set to zero to indicate free memory units.
  2. For allocation, iterate over the array to find the leftmost contiguous block of zeros of the required size. Track the start index of each potential free segment. Once a block is found, update the memory array by filling it with mID and return the starting index. If no such block exists, return -1.
  3. For freeing, iterate over the memory array. If an element equals the given mID, increment a counter and reset that position to zero. After completing the scan, return the counter as the number of units freed.
  4. Maintain the memory array throughout operations to ensure correctness for future allocations and frees.

Why it works: The memory array always reflects the current allocation state, and scanning from left to right guarantees allocation of the leftmost free block. Freeing by iterating over the array ensures all blocks associated with a given mID are released.

Python Solution

class Allocator:

    def __init__(self, n: int):
        self.memory = [0] * n

    def allocate(self, size: int, mID: int) -> int:
        n = len(self.memory)
        start = 0
        while start <= n - size:
            # Check if there is a free block of required size
            if all(self.memory[i] == 0 for i in range(start, start + size)):
                for i in range(start, start + size):
                    self.memory[i] = mID
                return start
            start += 1
        return -1

    def freeMemory(self, mID: int) -> int:
        freed = 0
        for i in range(len(self.memory)):
            if self.memory[i] == mID:
                self.memory[i] = 0
                freed += 1
        return freed

This implementation initializes a memory array with zeros. Allocation scans for the leftmost free block of required size, fills it with mID, and returns the starting index. Freeing iterates through the array, resets units with the specified mID, and counts freed units.

Go Solution

type Allocator struct {
	memory []int
}

func Constructor(n int) Allocator {
	return Allocator{
		memory: make([]int, n),
	}
}

func (this *Allocator) Allocate(size int, mID int) int {
	n := len(this.memory)
	for start := 0; start <= n-size; start++ {
		free := true
		for i := start; i < start+size; i++ {
			if this.memory[i] != 0 {
				free = false
				start = i // optimization: skip to next after occupied
				break
			}
		}
		if free {
			for i := start; i < start+size; i++ {
				this.memory[i] = mID
			}
			return start
		}
	}
	return -1
}

func (this *Allocator) FreeMemory(mID int) int {
	freed := 0
	for i := 0; i < len(this.memory); i++ {
		if this.memory[i] == mID {
			this.memory[i] = 0
			freed++
		}
	}
	return freed
}

In Go, the memory array is implemented as a slice of integers. The allocation function checks contiguous free blocks and updates the slice, while the free function iterates and resets memory units.

Worked Examples

Using the example from the problem:

Operation Memory State Return Value
Allocator(10) [0,0,0,0,0,0,0,0,0,0] null
allocate(1,1) [1,0,0,0,0,0,0,0,0,0] 0
allocate(1,2) [1,2,0,0,0,0,0,0,0,0] 1
allocate(1,3) [1,2,3,0,0,0,0,0,0,0] 2
freeMemory(2) [1,0,3,0,0,0,0,0,0,0] 1
allocate(3,4) [1,0,3,4,4,4,0,0,0,0] 3
allocate(1,1) [1,1,3,4,4,4,0,0,0,0] 1
allocate(1,1) [1,1,3,4,4,4,1,0,0,0] 6
freeMemory(1) [0,0,3,4,4,4,0,0,0,0] 3
allocate(10,2) [0,0,3,4,4,4,0,0,0,0] -1
freeMemory(7) [0,0,3,4,4,4,0,0,0,0] 0

Complexity Analysis

Measure Complexity Explanation
Time O(n) per operation Allocation scans memory array, freeing scans memory array
Space O(n) Memory array stores current allocation state

The array is small (n ≤ 1000), so the linear scan is acceptable. Optimizations using maps only reduce freeing cost slightly but do not change allocation complexity.

Test Cases

# Basic allocations
obj = Allocator(10)
assert obj.allocate(1,1) == 0  # leftmost free block
assert obj.allocate(1,2) == 1
assert obj.allocate(1,3) == 2
assert obj.freeMemory(2) == 1  # free ID 2
assert obj.allocate(3,4) == 3
assert obj.allocate(1,1) == 1  # reuse freed space
assert obj.allocate(1,1) == 6
assert obj.freeMemory(1) == 3
assert obj.allocate(10,2) == -1  # not enough space
assert obj.freeMemory(7) == 0  # no such ID

# Edge cases
obj2 = Allocator(1)
assert obj2.allocate(1,1) == 0
assert obj2.allocate(1,2) == -1  # memory full
assert obj2.freeMemory(1) == 1
assert obj2.allocate(1,2) == 0  # after freeing

obj3 = Allocator(5)
assert obj3