2502. Design Memory Allocator
On LeetCode ->Problem¶
Manage a 0-indexed memory array. Allocate the leftmost run of size free cells to mID, or return -1. Free all cells owned by an mID and return the number freed.
class Allocator:
def __init__(self, n: int):
pass
def allocate(self, size: int, mID: int) -> int:
pass
def freeMemory(self, mID: int) -> int:
pass
Key trick¶
Use bytearray.find() to locate a run of zero bytes in native code. Keep each ID's allocated blocks so freeing touches only those blocks.
Trap¶
An ID can own multiple blocks. Freeing it must count every cell, and freeing it again must return 0.
Why is it interesting?¶
The algorithm remains \(O(n)\) for allocation, but replacing a Python-level scan with a native-code search can make it substantially faster in practice.
Python solution¶
class Allocator:
def __init__(self, n: int):
self.memory = bytearray(n)
self.ids = {}
def allocate(self, size: int, mID: int) -> int:
if size > len(self.memory):
return -1
# A sequence of zero bytes represents consecutive free cells.
start = self.memory.find(bytes(size))
if start == -1:
return -1
self.memory[start:start + size] = b"\x01" * size
self.ids.setdefault(mID, []).append((start, size))
return start
def freeMemory(self, mID: int) -> int:
total = 0
for start, size in self.ids.pop(mID, []):
self.memory[start:start + size] = bytes(size)
total += size
return total
Allocation takes \(O(n)\) time. Freeing takes \(O(k + t)\) time for \(k\) blocks containing \(t\) cells. Space is \(O(n)\).
Comment on my solution¶
Your search for the leftmost free block works. The wrong answer comes from replacing self.ids[mID] on every allocation: ID 1 owns three cells in the example, but its record retains only the last one. Also, freeMemory never removes that record, so freeing the same ID again can return an incorrect count or erase a newer allocation.
Your revised solution correctly records and frees multiple blocks per ID. Its remaining bug is returning size from the last block instead of the sum of all freed block sizes. Using pop(mID, []) also handles an unknown or already-freed ID without a separate check.
# Wrong Answer: 50/109 testcases passed
# 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,1,-1,0]
# Expected: [null,0,1,2,1,3,1,6,3,-1,0]
class Allocator:
def __init__(self, n: int):
self.n = n
self.memory = [0] * n
self.ids = {} # mID -> [idx_start, size]
def allocate(self, size: int, mID: int) -> int:
i = 0
while i < self.n:
if self.memory[i]:
i += 1
continue
j = i + 1
while j - i != size and j < self.n and self.memory[j] == 0:
j += 1
if j - i == size:
self.memory[i:i + size] = [mID] * size
self.ids[mID] = [i, size]
return i
i = j
return -1
def freeMemory(self, mID: int) -> int:
if mID not in self.ids:
return 0
start, size = self.ids[mID]
self.memory[start:start + size] = [0] * size
return size
# Written after reading AI comments
# Wrong Answer: 106/109 testcases passed
# 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,1,-1,0]
# Expected: [null,0,1,2,1,3,1,6,3,-1,0]
class Allocator:
def __init__(self, n: int):
self.n = n
self.memory = [0] * n
self.ids = {} # mID -> [[idx_start, size], ...]
def allocate(self, size: int, mID: int) -> int:
i = 0
while i < self.n:
if self.memory[i]:
i += 1
continue
j = i + 1
while j - i != size and j < self.n and self.memory[j] == 0:
j += 1
if j - i == size:
self.memory[i:i + size] = [mID] * size
self.ids.setdefault(mID, []).append([i, size])
return i
i = j
return -1
def freeMemory(self, mID: int) -> int:
if mID not in self.ids:
return 0
for start, size in self.ids[mID]:
self.memory[start:start + size] = [0] * size
del self.ids[mID]
return size
# WORKS
# Written incorporating AI fix of `freeMemory`
class Allocator:
def __init__(self, n: int):
self.n = n
self.memory = [0] * n
self.ids = {} # mID -> [[idx_start, size], ...]
def allocate(self, size: int, mID: int) -> int:
i = 0
while i < self.n:
if self.memory[i]:
i += 1
continue
j = i + 1
while j - i != size and j < self.n and self.memory[j] == 0:
j += 1
if j - i == size:
self.memory[i:i + size] = [mID] * size
self.ids.setdefault(mID, []).append([i, size])
return i
i = j
return -1
def freeMemory(self, mID: int) -> int:
total = 0
for start, size in self.ids.pop(mID, []):
self.memory[start:start + size] = [0] * size
total += size
return total