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:
size consecutive free memory units and assign it the id mID.mID.Note that:
mID.mID, even if they were allocated in different blocks.Implement the Allocator class:
Allocator(int n) Initializes an Allocator object with a memory array of size n.int allocate(int size, int mID) Find the leftmost block of size consecutive free memory units and allocate it with the id mID. 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 id mID. 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 <= 10001000 calls will be made to allocate and freeMemory.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.
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.
The C solution uses a structure Allocator that includes an array to represent memory and an integer to denote its size. Each memory unit is initialized to 0 indicating it's free. The allocate function iterates over the array, attempting to find a contiguous block of the necessary size that is free (denoted by 0). If found, it marks this block with the given mID. The freeMemory function resets any block with the target mID to 0, indicating it is free.
Time Complexity: O(n * m), where n is the size of the memory and m is the size required, in the worst case.
Space Complexity: O(1), aside from the input size.
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.
Example Language Placeholder
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.
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.
Python
Java
C++
Go
TypeScript
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.
| Approach | Complexity |
|---|---|
| Array-Based Approach | Time Complexity: O(n * m), where n is the size of the memory and m is the size required, in the worst case. |
| 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 | — |
| 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 |
Leetcode 2502: Design Memory Allocator • Algorithms Casts • 2,256 views views
Watch 9 more video solutions →Practice Design Memory Allocator with our built-in code editor and test cases.
Practice on FleetCode