In this guide, you will get 2502. Design Memory Allocator LeetCode Solution with the best time and space complexity. The solution to Design Memory Allocator problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 size consecutive free memory units and assign it the id mID.
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 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.
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.
1 <= n, size, mID <= 1000
At most 1000 calls will be made to allocate and freeMemory.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n + 1000)
2502. Design Memory Allocator LeetCode Solution in C++
class Allocator {
public:
Allocator(int n) : memory(n), mIDToIndices(1001) {}
int allocate(int size, int mID) {
int consecutiveFree = 0;
for (int i = 0; i < memory.size(); ++i) {
consecutiveFree = memory[i] == 0 ? consecutiveFree + 1 : 0;
if (consecutiveFree == size) {
for (int j = i - consecutiveFree + 1; j <= i; ++j) {
memory[j] = mID;
mIDToIndices[mID].push_back(j);
}
return i - consecutiveFree + 1;
}
}
return -1;
}
int free(int mID) {
vector<int>& indices = mIDToIndices[mID];
const int freedUnits = indices.size();
for (const int index : indices)
memory[index] = 0;
indices.clear();
return freedUnits;
}
private:
vector<int> memory;
vector<vector<int>> mIDToIndices;
}; /* code provided by PROGIEZ */
2502. Design Memory Allocator LeetCode Solution in Java
class Allocator {
public Allocator(int n) {
memory = new int[n];
mIDToIndices = new List[1001];
for (int i = 1; i <= 1000; ++i)
mIDToIndices[i] = new ArrayList<>();
}
public int allocate(int size, int mID) {
int consecutiveFree = 0;
for (int i = 0; i < memory.length; ++i) {
consecutiveFree = memory[i] == 0 ? consecutiveFree + 1 : 0;
if (consecutiveFree == size) {
for (int j = i - consecutiveFree + 1; j <= i; ++j) {
memory[j] = mID;
mIDToIndices[mID].add(j);
}
return i - consecutiveFree + 1;
}
}
return -1;
}
public int free(int mID) {
List<Integer> indices = mIDToIndices[mID];
final int freedUnits = indices.size();
for (final int index : indices)
memory[index] = 0;
indices.clear();
return freedUnits;
}
private int[] memory;
private List<Integer>[] mIDToIndices;
} // code provided by PROGIEZ
2502. Design Memory Allocator LeetCode Solution in Python
class Allocator:
def __init__(self, n: int):
self.memory = [0] * n
self.mIDToIndices = [[] for _ in range(1001)]
def allocate(self, size: int, mID: int) -> int:
consecutiveFree = 0
for i, m in enumerate(self.memory):
consecutiveFree = consecutiveFree + 1 if m == 0 else 0
if consecutiveFree == size:
for j in range(i - consecutiveFree + 1, i + 1):
self.memory[j] = mID
self.mIDToIndices[mID].append(j)
return i - consecutiveFree + 1
return -1
def free(self, mID: int) -> int:
indices = self.mIDToIndices[mID]
freedUnits = len(indices)
for index in indices:
self.memory[index] = 0
indices.clear()
return freedUnits # code by PROGIEZ
