Skip to content

2502. Design Memory Allocator

  • Time:
    • Constructor: $O(n + 1000)$
    • allocate(size: int, mID: int): $O(n)$
    • free(mID: int): $O(n)$
  • Space: $O(n + 1000)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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