##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2502.html

# 2502. Design Memory Allocator

## Description

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:

1. Allocate a block of size consecutive free memory units and assign it the id mID.
2. 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 free(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", "free", "allocate", "allocate", "allocate", "free", "allocate", "free"]
[[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.free(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.free(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.free(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 1000 calls will be made to allocate and free.

## Solutions

• class Allocator {
private TreeMap<Integer, Integer> tm = new TreeMap<>();
private Map<Integer, List<Integer>> d = new HashMap<>();

public Allocator(int n) {
tm.put(-1, -1);
tm.put(n, n);
}

public int allocate(int size, int mID) {
int s = -1;
for (var entry : tm.entrySet()) {
int v = entry.getKey();
if (s != -1) {
int e = v - 1;
if (e - s + 1 >= size) {
tm.put(s, s + size - 1);
return s;
}
}
s = entry.getValue() + 1;
}
return -1;
}

public int free(int mID) {
int ans = 0;
for (int s : d.getOrDefault(mID, Collections.emptyList())) {
int e = tm.remove(s);
ans += e - s + 1;
}
d.remove(mID);
return ans;
}
}

/**
* Your Allocator object will be instantiated and called as such:
* Allocator obj = new Allocator(n);
* int param_1 = obj.allocate(size,mID);
* int param_2 = obj.free(mID);
*/

• class Allocator {
public:
Allocator(int n) {
tm[-1] = -1;
tm[n] = n;
}

int allocate(int size, int mID) {
int s = -1;
for (auto& [v, c] : tm) {
if (s != -1) {
int e = v - 1;
if (e - s + 1 >= size) {
tm[s] = s + size - 1;
d[mID].emplace_back(s);
return s;
}
}
s = c + 1;
}
return -1;
}

int free(int mID) {
int ans = 0;
for (int& s : d[mID]) {
int e = tm[s];
tm.erase(s);
ans += e - s + 1;
}
d.erase(mID);
return ans;
}

private:
map<int, int> tm;
unordered_map<int, vector<int>> d;
};

/**
* Your Allocator object will be instantiated and called as such:
* Allocator* obj = new Allocator(n);
* int param_1 = obj->allocate(size,mID);
* int param_2 = obj->free(mID);
*/

• from sortedcontainers import SortedList

class Allocator:
def __init__(self, n: int):
self.sl = SortedList([(-1, -1), (n, n)])
self.d = defaultdict(list)

def allocate(self, size: int, mID: int) -> int:
for (_, s), (e, _) in pairwise(self.sl):
s, e = s + 1, e - 1
if e - s + 1 >= size:
self.sl.add((s, s + size - 1))
self.d[mID].append((s, s + size - 1))
return s
return -1

def free(self, mID: int) -> int:
ans = 0
for block in self.d[mID]:
self.sl.remove(block)
ans += block[1] - block[0] + 1
del self.d[mID]
return ans

# Your Allocator object will be instantiated and called as such:
# obj = Allocator(n)
# param_1 = obj.allocate(size,mID)
# param_2 = obj.free(mID)


• 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) Free(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.Free(mID);
*/