Design Memory Allocator

Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


**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 1000 calls will be made to allocate and freeMemory.

Solution

Method 1 – Linear Scan with Array

Intuition

We can use a simple array to represent the memory, where each cell stores the mID or 0 for free. To allocate, scan for the leftmost block of consecutive free cells. To free, scan and reset all cells with the given mID.

Approach

Use an array mem of size n, initialized to 0 (free).
For allocate(size, mID), scan from left to right for the first block of size consecutive 0s. If found, set those cells to mID and return the start index; else return -1.
For freeMemory(mID), scan the array and set all cells with value mID to 0, counting the number of cells freed. Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Allocator {
    vector<int> mem;
public:
    Allocator(int n) : mem(n, 0) {}
    int allocate(int size, int mID) {
        for (int i = 0; i + size <= mem.size(); ++i) {
            bool ok = true;
            for (int j = 0; j < size; ++j) if (mem[i+j]) { ok = false; break; }
            if (ok) {
                for (int j = 0; j < size; ++j) mem[i+j] = mID;
                return i;
            }
        }
        return -1;
    }
    int freeMemory(int mID) {
        int cnt = 0;
        for (int& x : mem) if (x == mID) { x = 0; cnt++; }
        return cnt;
    }
};

 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


type Allocator struct {
    mem []int
}
func Constructor(n int) Allocator {
    return Allocator{mem: make([]int, n)}
}
func (a *Allocator) Allocate(size, mID int) int {
    for i := 0; i+size <= len(a.mem); i++ {
        ok := true
        for j := 0; j < size; j++ {
            if a.mem[i+j] != 0 {
                ok = false
                break
            }
        }
        if ok {
            for j := 0; j < size; j++ {
                a.mem[i+j] = mID
            }
            return i
        }
    }
    return -1
}
func (a *Allocator) FreeMemory(mID int) int {
    cnt := 0
    for i := range a.mem {
        if a.mem[i] == mID {
            a.mem[i] = 0
            cnt++
        }
    }
    return cnt
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


public class Allocator {
    private int[] mem;
    public Allocator(int n) {
        mem = new int[n];
    }
    public int allocate(int size, int mID) {
        for (int i = 0; i + size <= mem.length; ++i) {
            boolean ok = true;
            for (int j = 0; j < size; ++j) if (mem[i+j] != 0) { ok = false; break; }
            if (ok) {
                for (int j = 0; j < size; ++j) mem[i+j] = mID;
                return i;
            }
        }
        return -1;
    }
    public int freeMemory(int mID) {
        int cnt = 0;
        for (int i = 0; i < mem.length; ++i) if (mem[i] == mID) { mem[i] = 0; cnt++; }
        return cnt;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Allocator(n: Int) {
    private val mem = IntArray(n)
    fun allocate(size: Int, mID: Int): Int {
        for (i in 0..mem.size - size) {
            if ((0 until size).all { mem[i+it] == 0 }) {
                for (j in 0 until size) mem[i+j] = mID
                return i
            }
        }
        return -1
    }
    fun freeMemory(mID: Int): Int {
        var cnt = 0
        for (i in mem.indices) if (mem[i] == mID) { mem[i] = 0; cnt++ }
        return cnt
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Allocator:
    def __init__(self, n: int):
        self.mem = [0] * n
    def allocate(self, size: int, mID: int) -> int:
        for i in range(len(self.mem) - size + 1):
            if all(x == 0 for x in self.mem[i:i+size]):
                for j in range(i, i+size):
                    self.mem[j] = mID
                return i
        return -1
    def freeMemory(self, mID: int) -> int:
        cnt = 0
        for i in range(len(self.mem)):
            if self.mem[i] == mID:
                self.mem[i] = 0
                cnt += 1
        return cnt

 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


struct Allocator {
    mem: Vec<i32>,
}
impl Allocator {
    fn new(n: i32) -> Self {
        Self { mem: vec![0; n as usize] }
    }
    fn allocate(&mut self, size: i32, mID: i32) -> i32 {
        let n = self.mem.len();
        for i in 0..=n - size as usize {
            if self.mem[i..i+size as usize].iter().all(|&x| x == 0) {
                for j in i..i+size as usize {
                    self.mem[j] = mID;
                }
                return i as i32;
            }
        }
        -1
    }
    fn free_memory(&mut self, mID: i32) -> i32 {
        let mut cnt = 0;
        for x in self.mem.iter_mut() {
            if *x == mID {
                *x = 0;
                cnt += 1;
            }
        }
        cnt
    }
}

 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


class Allocator {
    private mem: number[];
    constructor(n: number) {
        this.mem = Array(n).fill(0);
    }
    allocate(size: number, mID: number): number {
        for (let i = 0; i + size <= this.mem.length; ++i) {
            if (this.mem.slice(i, i+size).every(x => x === 0)) {
                for (let j = i; j < i+size; ++j) this.mem[j] = mID;
                return i;
            }
        }
        return -1;
    }
    freeMemory(mID: number): number {
        let cnt = 0;
        for (let i = 0; i < this.mem.length; ++i) {
            if (this.mem[i] === mID) {
                this.mem[i] = 0;
                cnt++;
            }
        }
        return cnt;
    }
}

Complexity

⏰ Time complexity: O(n*size) for allocate, O(n) for freeMemory, where n is the memory size.
🧺 Space complexity: O(n), for the memory array.

Problem#

Examples#

Example 1#

Constraints#

Solution#

Method 1 – Linear Scan with Array#

Intuition#

Approach#

Code#

Complexity#