Problem statement

A memory of n units is indexed 0 to n - 1, all free at the start. Write the class Allocator:

• Allocator(int n) creates the memory.
• int allocate(int size, int mID) finds the leftmost run of size consecutive free units, marks them as owned by mID, and returns the index of the run's first unit. If no such run exists it returns -1 and changes nothing.
• int freeMemory(int mID) frees every unit owned by mID and returns how many units that was.

The same mID may be used by several allocations; all of its units are freed together. An mID that owns nothing frees 0 units.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

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: Units 0, 1, 2 go to ids 1, 2, 3. Freeing id 2 opens unit 1, but the three-unit block for id 4 must start at 3. The next two single units for id 1 take 1 and then 6. Freeing id 1 releases units 0, 1 and 6. Ten units are no longer free in a row, and id 7 owns nothing.

Example 2

Input: ["Allocator","allocate","allocate","freeMemory","allocate","allocate"]
[[5],[5,9],[1,3],[9],[2,4],[4,4]]
Output: [null,0,-1,5,0,-1]
Explanation: Id 9 fills the whole memory, so the next request fails. Once it is freed, id 4 gets units 0–1; only units 2–4 are left free, so the request for four more fails.

Constraints

• 1 <= n, size, mID <= 1000
• At most 1000 calls are made in total to allocate and freeMemory

Hints for Design Memory Allocator

1. Hint 1

   With n and the number of calls both at most 1000, an O(n) scan per call is fast enough.

2. Hint 2

   Store, for each unit, the id that owns it (0 for free).

3. Hint 3

   For allocate, walk the units counting the current run of free ones; the moment the run reaches size, the block ends here and starts size - 1 units earlier.

How to solve Design Memory Allocator

Keep an array owner[0..n-1] (0 = free). Allocation is one left-to-right pass that tracks the length of the current free run; freeing is one pass that clears every unit with that id.

Approach

1. allocate(size, mID): let run = 0; for each unit i, set run = run + 1 if owner[i] == 0, else run = 0. When run == size, fill owner[i - size + 1 .. i] with mID and return i - size + 1.
2. If the pass ends without a run of size, return -1.
3. freeMemory(mID): clear every unit whose owner is mID, counting them, and return the count.

Why it works

The first index at which a free run reaches length size is the end of the leftmost block of size free units: any block that starts earlier would have completed its run earlier. Freeing by scanning catches every unit of an id even when it came from several separate allocations.

Complexity

• Time — O(n) per call
• Space — O(n)

Pitfalls

• Ids are not unique per allocation — free all of an id's units, not just one block.
• A failed allocation must not mark any unit.

Reference solution

Python

class Allocator:

    def __init__(self, n: int):
        self.owner = [0] * n  # 0 means free

    def allocate(self, size: int, mID: int) -> int:
        run = 0
        for i, o in enumerate(self.owner):
            run = run + 1 if o == 0 else 0
            if run == size:
                start = i - size + 1
                self.owner[start:i + 1] = [mID] * size
                return start
        return -1

    def freeMemory(self, mID: int) -> int:
        freed = 0
        for i, o in enumerate(self.owner):
            if o == mID:
                self.owner[i] = 0
                freed += 1
        return freed

Java

class Allocator {
    private int[] owner; // 0 means free

    public Allocator(int n) {
        owner = new int[n];
    }

    public int allocate(int size, int mID) {
        int run = 0;
        for (int i = 0; i < owner.length; i++) {
            run = owner[i] == 0 ? run + 1 : 0;
            if (run == size) {
                for (int j = i - size + 1; j <= i; j++) owner[j] = mID;
                return i - size + 1;
            }
        }
        return -1;
    }

    public int freeMemory(int mID) {
        int freed = 0;
        for (int i = 0; i < owner.length; i++) {
            if (owner[i] == mID) { owner[i] = 0; freed++; }
        }
        return freed;
    }
}

C++

class Allocator {
    vector<int> owner; // 0 means free
public:
    Allocator(int n) : owner(n, 0) {}

    int allocate(int size, int mID) {
        int run = 0;
        for (int i = 0; i < (int)owner.size(); i++) {
            run = owner[i] == 0 ? run + 1 : 0;
            if (run == size) {
                for (int j = i - size + 1; j <= i; j++) owner[j] = mID;
                return i - size + 1;
            }
        }
        return -1;
    }

    int freeMemory(int mID) {
        int freed = 0;
        for (int& o : owner) {
            if (o == mID) { o = 0; freed++; }
        }
        return freed;
    }
};

JavaScript

var Allocator = function(n) {
    this.owner = new Int32Array(n); // 0 means free
};

Allocator.prototype.allocate = function(size, mID) {
    var run = 0;
    for (var i = 0; i < this.owner.length; i++) {
        run = this.owner[i] === 0 ? run + 1 : 0;
        if (run === size) {
            for (var j = i - size + 1; j <= i; j++) this.owner[j] = mID;
            return i - size + 1;
        }
    }
    return -1;
};

Allocator.prototype.freeMemory = function(mID) {
    var freed = 0;
    for (var i = 0; i < this.owner.length; i++) {
        if (this.owner[i] === mID) { this.owner[i] = 0; freed++; }
    }
    return freed;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium
• Simple Bank System Medium