Design Memory Allocator - Video Solutions
Leetcode 2502: Design Memory Allocator
Design Memory Allocator - Video Solution
Watch 10 video solutions for Design Memory Allocator, a medium level problem involving Array, Hash Table, Design. This walkthrough by Algorithms Casts has 2,553 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
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 |