Design Memory Allocator solution and explanation
Google
9 more videos on this problem
Leetcode 2502: Design Memory AllocatorAlgorithms Casts · 15:25 · 2K views
2502. Design Memory Allocator (Leetcode Medium)Programming Live with Larry · 15:01 · 1K views
2502. Design Memory Allocator | Weekly Contest 323 | LeetCode 2502Bro Coders · 5:58 · 1K views
Design Memory Allocator | 2502 LeetCode | Brute Force | Leetcode Weekly Contest 323CodeWithSunny · 10:38 · 955 views
[HARDER Version] Design Memory Allocator | Weekly Contest 323codingMohan · 23:58 · 779 views
Weekly Contest 323 | Design Memory AllocatorcodingMohan · 11:27 · 560 views
Leetcode 2502 Design Memory AllocatorAlgorithmicIQ · 20:09 · 556 views
Leetcode 2502 Design Memory Allocator - HindiThinkCode · 9:46 · 517 views
LeetCode 2502. Design Memory Allocator | Simple Explanation with CodeDeep Tech · 8:19 · 433 views
Design Memory Allocator | leetcode Weekly 323 | Leetcode MediumBinaryMagic · 10:34 · 357 views
The problem
You are given an integer n representing the size of a 0-indexed memory array. All memory units are initially free.
You have a memory allocator with the following functionalities:
- Allocate a block of
sizeconsecutive free memory units and assign it the idmID. - Free all memory units with the given id
mID.
Note that:
- Multiple blocks can be allocated to the same
mID. - You should free all the memory units with
mID, even if they were allocated in different blocks.
Implement the Allocator class:
Allocator(int n)Initializes anAllocatorobject with a memory array of sizen.int allocate(int size, int mID)Find the leftmost block ofsizeconsecutive free memory units and allocate it with the idmID. Return the block's first index. If such a block does not exist, return-1.int freeMemory(int mID)Free all memory units with the idmID. Return the number of memory units you have freed.
Example 1:
Input ["Allocator", "allocate", "allocate", "allocate", "freeMemory", "allocate", "allocate", "allocate", "freeMemory", "allocate", "freeMemory"] [[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]] Output [null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0] Explanation Allocator loc = new Allocator(10); // Initialize a memory array of size 10. All memory units are initially free. loc.allocate(1, 1); // The leftmost block's first index is 0. The memory array becomes [1,_,_,_,_,_,_,_,_,_]. We return 0. loc.allocate(1, 2); // The leftmost block's first index is 1. The memory array becomes [1,2,_,_,_,_,_,_,_,_]. We return 1. loc.allocate(1, 3); // The leftmost block's first index is 2. The memory array becomes [1,2,3,_,_,_,_,_,_,_]. We return 2. loc.freeMemory(2); // Free all memory units with mID 2. The memory array becomes [1,_, 3,_,_,_,_,_,_,_]. We return 1 since there is only 1 unit with mID 2. loc.allocate(3, 4); // The leftmost block's first index is 3. The memory array becomes [1,_,3,4,4,4,_,_,_,_]. We return 3. loc.allocate(1, 1); // The leftmost block's first index is 1. The memory array becomes [1,1,3,4,4,4,_,_,_,_]. We return 1. loc.allocate(1, 1); // The leftmost block's first index is 6. The memory array becomes [1,1,3,4,4,4,1,_,_,_]. We return 6. loc.freeMemory(1); // Free all memory units with mID 1. The memory array becomes [_,_,3,4,4,4,_,_,_,_]. We return 3 since there are 3 units with mID 1. loc.allocate(10, 2); // We can not find any free block with 10 consecutive free memory units, so we return -1. loc.freeMemory(7); // Free all memory units with mID 7. The memory array remains the same since there is no memory unit with mID 7. We return 0.
Constraints:
1 <= n, size, mID <= 1000- At most
1000calls will be made toallocateandfreeMemory.
Approach overview
Problem Overview: You need to simulate a memory allocator that manages n memory slots. The allocate(size, mID) operation finds the leftmost contiguous block of free slots of length size and marks them with mID. The free(mID) operation releases all slots assigned to that ID and returns the number of freed cells.
Approach 1: Array-Based Simulation (O(n) allocate, O(n) free)
The simplest design uses a fixed array of size n where each index stores the current mID occupying that memory slot or 0 if the slot is free. For allocate, iterate through the array and look for the first contiguous window of size empty cells. Once found, fill those cells with mID and return the starting index. If no such window exists, return -1. For free(mID), scan the entire array and reset every cell that equals mID back to 0, counting how many slots were released.
This approach works because the constraints allow a straightforward simulation. The main operations are sequential scans and updates, making the logic easy to implement and debug. It fits well with problems tagged under simulation and design, where the goal is to mirror the real-world system behavior directly. Time complexity for both operations is O(n), while space complexity is O(n) for the memory array.
Approach 2: Linked List of Free Blocks (O(k) allocate, O(k) free)
A more structured design keeps track of free memory segments using a linked list of intervals. Each node stores a free block represented by [start, length]. During allocate, traverse the list and pick the first block whose length is at least size. Allocate from its start, shrink the interval, and remove the node if the block becomes empty. To support efficient free operations, maintain a hash table mapping mID to the segments allocated to that ID.
When freeing memory, retrieve all segments associated with mID, insert them back into the free list, and merge adjacent intervals to prevent fragmentation. The complexity depends on the number of tracked blocks k. Allocation and freeing both run in roughly O(k), and the additional storage for the mapping and interval list results in O(n) space overall.
Recommended for interviews: The array-based simulation is usually expected first because it directly models the allocator and demonstrates clear reasoning. After presenting it, discussing the linked list interval design shows deeper system design thinking and awareness of fragmentation and memory management trade‑offs.
Approach 1: Array-Based Approach
This approach uses an array to represent the memory. Each slot in the array can store an integer corresponding to the memory ID (mID) allocated to it, or 0 if it is free. Allocation involves finding the first contiguous subarray of the required size that is free, and marking it with the given mID. Freeing memory involves iterating over the entire array and setting slots to 0 wherever the mID matches the given parameter.
class Allocator:
def __init__(self, n: int):
self.memory = [0] * n
def allocate(self, size: int, mID: int) -> int:
n = len(self.memory)
for i in range(n - size + 1):
if all(self.memory[j] == 0 for j in range(i, i + size)):
for j in range(i, i + size):
self.memory[j] = mID
return i
return -1
def freeMemory(self, mID: int) -> int:
freed = sum(1 for i in range(len(self.memory)) if self.memory[i] == mID)
self.memory = [0 if x == mID else x for x in self.memory]
return freedclass Allocator {
private int[] memory;
private int size;
public Allocator(int n) {
this.memory = new int[n];
this.size = n;
}
public int allocate(int size, int mID) {
for (int i = 0; i <= this.size - size; i++) {
if (isFree(i, size)) {
for (int j = 0; j < size; j++) {
memory[i + j] = mID;
}
return i;
}
}
return -1;
}
public int freeMemory(int mID) {
int freed = 0;
for (int i = 0; i < this.size; i++) {
if (memory[i] == mID) {
memory[i] = 0;
freed++;
}
}
return freed;
}
private boolean isFree(int index, int size) {
for (int i = index; i < index + size; i++) {
if (memory[i] != 0) {
return false;
}
}
return true;
}
}#include <vector>
class Allocator {
public:
Allocator(int n) : memory(n, 0), size(n) {}
int allocate(int size, int mID) {
for (int i = 0; i <= this->size - size; ++i) {
if (isFree(i, size)) {
std::fill(memory.begin() + i, memory.begin() + i + size, mID);
return i;
}
}
return -1;
}
int freeMemory(int mID) {
int freed = 0;
for (int &unit : memory) {
if (unit == mID) {
unit = 0;
++freed;
}
}
return freed;
}
private:
std::vector<int> memory;
int size;
bool isFree(int index, int size) {
for (int i = index; i < index + size; ++i) {
if (memory[i] != 0) return false;
}
return true;
}
};class Allocator {
constructor(n) {
this.memory = new Array(n).fill(0);
}
allocate(size, mID) {
for (let i = 0; i <= this.memory.length - size; i++) {
if (this.memory.slice(i, i + size).every(x => x === 0)) {
for (let j = 0; j < size; j++) {
this.memory[i + j] = mID;
}
return i;
}
}
return -1;
}
freeMemory(mID) {
let freed = 0;
for (let i = 0; i < this.memory.length; i++) {
if (this.memory[i] === mID) {
this.memory[i] = 0;
freed++;
}
}
return freed;
}
}#include <stdlib.h>
typedef struct {
int* memory;
int size;
} Allocator;
Allocator* allocatorCreate(int n) {
Allocator* obj = (Allocator*)malloc(sizeof(Allocator));
obj->memory = (int*)calloc(n, sizeof(int));
obj->size = n;
return obj;
}
int allocatorAllocate(Allocator* obj, int size, int mID) {
for (int i = 0; i <= obj->size - size; i++) {
int free = 1;
for (int j = 0; j < size; j++) {
if (obj->memory[i + j] != 0) {
free = 0;
break;
}
}
if (free) {
for (int j = 0; j < size; j++) {
obj->memory[i + j] = mID;
}
return i;
}
}
return -1;
}
int allocatorFreeMemory(Allocator* obj, int mID) {
int freed = 0;
for (int i = 0; i < obj->size; i++) {
if (obj->memory[i] == mID) {
obj->memory[i] = 0;
freed++;
}
}
return freed;
}
void allocatorFree(Allocator* obj) {
free(obj->memory);
free(obj);
}public class Allocator {
private int[] memory;
public Allocator(int n) {
memory = new int[n];
}
public int Allocate(int size, int mID) {
for (int i = 0; i <= memory.Length - size; i++) {
bool isFree = true;
for (int j = i; j < i + size; j++) {
if (memory[j] != 0) {
isFree = false;
break;
}
}
if (isFree) {
for (int j = i; j < i + size; j++) {
memory[j] = mID;
}
return i;
}
}
return -1;
}
public int FreeMemory(int mID) {
int freed = 0;
for (int i = 0; i < memory.Length; i++) {
if (memory[i] == mID) {
memory[i] = 0;
freed++;
}
}
return freed;
}
}In Python, we use a list to represent memory blocks, initialized to 0 indicating they are free. The allocate function checks for a sequence of zeros in the list. Once a sufficient sequence is found, it assigns the mID to those indices and returns the starting index. If no sequence is found, it returns -1. The freeMemory function replaces occurrences of mID with 0 and counts them.
Time Complexity: O(n * m) for allocation, O(n) for freeing where n is the number of memory blocks.
Space Complexity: O(1) additional space usage aside from list initialization.
Approach 2: Linked List-Based Approach
An alternative implementation uses a linked list to represent memory blocks. Each node has an mID and a size, denoting a block of memory. Operations track free and allocated nodes using the linked list's structure, checking adjacent nodes to manage allocations efficiently. This allows for easy division, coalescence, and traversal of memory.
This solution uses linked list nodes each representing a block of memory, allowing adaptive management for allocation and deallocation demands. Managing blocks in this way can help reduce fragmentation by coalescing adjacent free nodes.
Time Complexity: Typically more efficient with O(log n) operations possible through adjustments. However, specifics depend on the implementation's management of linked list nodes, merging, and splitting behavior.
Space Complexity: Depends on data structure, primarily on total blocks managed.
Approach 3: Simulation
The data range of the problem is not large, so we can directly use an array to simulate the memory space.
During initialization, set each element in the array to 0, indicating it's free.
When the allocate method is called, traverse the array, find size consecutive free memory units, set them to mID, and return the first index.
When the free method is called, traverse the array, set all memory units equal to mID to 0, indicating they are free.
The time complexity is O(n times q), and the space complexity is O(n), where n and q are the size of the memory space and the number of method calls, respectively.
class Allocator {
private m: number[];
constructor(n: number) {
this.m = Array(n).fill(0);
}
allocate(size: number, mID: number): number {
let cnt = 0;
for (let i = 0; i < this.m.length; i++) {
if (this.m[i] > 0) {
cnt = 0;
} else if (++cnt === size) {
for (let j = i - size + 1; j <= i; j++) {
this.m[j] = mID;
}
return i - size + 1;
}
}
return -1;
}
freeMemory(mID: number): number {
let ans = 0;
for (let i = 0; i < this.m.length; i++) {
if (this.m[i] === mID) {
this.m[i] = 0;
ans++;
}
}
return ans;
}
}
/**
* Your Allocator object will be instantiated and called as such:
* var obj = new Allocator(n)
* var param_1 = obj.allocate(size,mID)
* var param_2 = obj.freeMemory(mID)
*/type Allocator struct {
m []int
}
func Constructor(n int) Allocator {
return Allocator{m: make([]int, n)}
}
func (this *Allocator) Allocate(size int, mID int) int {
cnt := 0
for i := 0; i < len(this.m); i++ {
if this.m[i] > 0 {
cnt = 0
} else if cnt++; cnt == size {
for j := i - size + 1; j <= i; j++ {
this.m[j] = mID
}
return i - size + 1
}
}
return -1
}
func (this *Allocator) FreeMemory(mID int) int {
ans := 0
for i := 0; i < len(this.m); i++ {
if this.m[i] == mID {
this.m[i] = 0
ans++
}
}
return ans
}
/**
* Your Allocator object will be instantiated and called as such:
* obj := Constructor(n);
* param_1 := obj.Allocate(size,mID);
* param_2 := obj.FreeMemory(mID);
*/Approach 4: Hash Table + Ordered Set
We can use an ordered set to maintain the start and end indices of all allocated memory units, where the start index is the key and the end index is the value. Additionally, we use a hash table to maintain the mID and its corresponding start index of the memory unit.
When the allocate method is called, we traverse the ordered set, find the first free interval with a length greater than or equal to size, allocate it to mID, and update the ordered set. Then we add the mID and its corresponding start index of the memory unit to the hash table.
When the free method is called, we find the start index of the memory unit corresponding to mID from the hash table, then delete it from the ordered set, and then delete mID from the hash table.
The time complexity is O(q log n), and the space complexity is O(n), where n and q are the size of the memory space and the number of method calls, respectively.
type Allocator struct {
rbt *redblacktree.Tree
d map[int][]int
}
func Constructor(n int) Allocator {
rbt := redblacktree.NewWithIntComparator()
rbt.Put(-1, -1)
rbt.Put(n, n)
return Allocator{rbt, map[int][]int{}}
}
func (this *Allocator) Allocate(size int, mID int) int {
s := -1
it := this.rbt.Iterator()
for it.Next() {
v := it.Key().(int)
if s != -1 {
e := v - 1
if e-s+1 >= size {
this.rbt.Put(s, s+size-1)
this.d[mID] = append(this.d[mID], s)
return s
}
}
s = it.Value().(int) + 1
}
return -1
}
func (this *Allocator) FreeMemory(mID int) int {
ans := 0
for _, s := range this.d[mID] {
if e, ok := this.rbt.Get(s); ok {
this.rbt.Remove(s)
ans += e.(int) - s + 1
}
}
this.d[mID] = []int{}
return ans
}
/**
* Your Allocator object will be instantiated and called as such:
* obj := Constructor(n);
* param_1 := obj.Allocate(size,mID);
* param_2 := obj.FreeMemory(mID);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Array-Based Approach | Time Complexity: O(n * m) for allocation, O(n) for freeing where n is the number of memory blocks. |
| Linked List-Based Approach | Time Complexity: Typically more efficient with O(log n) operations possible through adjustments. However, specifics depend on the implementation's management of linked list nodes, merging, and splitting behavior. |
| Simulation | – |
| Hash Table + Ordered Set | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array-Based Simulation | O(n) allocate, O(n) free | O(n) | Best for simple implementation and typical interview solutions |
| Linked List Free Block Tracking | O(k) allocate, O(k) free | O(n) | Useful when tracking memory segments and reducing fragmentation |
Frequently asked questions
Is Design Memory Allocator easy or hard?
Design Memory Allocator is generally rated Medium difficulty. The challenge is not complex algorithms but careful simulation of memory behavior, handling contiguous allocation correctly, and implementing efficient freeing of memory blocks.
Design Memory Allocator Python/Java solution
The problem can be implemented in multiple languages including Python, Java, C++, JavaScript, and C#. All implementations follow the same idea: maintain an array for memory slots, scan for contiguous free space during allocation, and reset slots during free operations.
How to solve Design Memory Allocator in O(n)?
Maintain an array representing memory slots. For allocate(size, mID), iterate through the array and check each possible starting position for a contiguous block of size free cells. Once found, mark those cells with mID. For free(mID), scan the array and reset all cells that match the given ID.
What is the best approach for Design Memory Allocator?
The most common solution uses an array to simulate memory. You scan the array to find the first contiguous block of free cells for allocation and scan again to free cells by mID. Both operations run in O(n) time with O(n) space, and the logic closely matches the problem requirements.
Is Design Memory Allocator asked at Google/Amazon/Meta?
Memory management simulation problems frequently appear in system design and coding interviews at large tech companies. Variants of allocator design and interval management have been reported in interviews at companies like Amazon and Google.
What data structure is used in Design Memory Allocator?
The typical solution uses an array to represent memory and simulate allocation. More advanced implementations may use linked lists to track free intervals and a hash map to store allocations associated with each mID.
What is the time complexity of Design Memory Allocator?
Using the standard array simulation approach, allocate runs in O(n) time because it scans the memory to find a contiguous block. The free operation also runs in O(n) because every slot may need to be checked. Space complexity is O(n) for storing the memory state.