Design Memory Allocator

Medium Design Data Structures Simulation Original on LeetCode

Design Memory Allocator is a medium design data structures problem solved with the simulation pattern. The best approach, optimal (free-segment list + ownership map), runs in O(f) per allocate, O(b · f) per freeMemory time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (owner per cell) up.

Problem

You manage a block of memory with n cells, indexed 0 to n - 1, all free at the start. Implement the Allocator class:

  • Allocator(int n) creates the memory with n free cells.
  • int allocate(int size, int mID) finds the leftmost run of size consecutive free cells, assigns all of them to the id mID and returns the index of the first cell. If no such run exists, it returns -1.
  • int freeMemory(int mID) frees every cell currently assigned to mID and returns how many cells were freed.

The same id may be used for several allocations, and its blocks do not need to be next to each other. Freeing an id releases all of them at once.

Examples

Example 1

Input
Allocator(8), allocate(3, 7), allocate(2, 4), allocate(2, 7), freeMemory(4), allocate(3, 9), freeMemory(7), allocate(9, 1)
Output
null, 0, 3, 5, 2, -1, 5, -1
Why
After freeing id 4, cells 3–4 are free but only 2 long and cell 7 is a single free cell, so a block of 3 does not fit. Freeing id 7 releases 5 cells; 9 cells never fit in a memory of 8.

Example 2

Input
Allocator(5), allocate(2, 1), allocate(2, 2), freeMemory(1), allocate(1, 3), allocate(2, 3), freeMemory(3), freeMemory(3)
Output
null, 0, 2, 2, 0, -1, 1, 0
Why
The leftmost free block is used first, so id 3 gets cell 0. A block of 2 then fails because only cells 1 and 4 are free and they are not adjacent. Freeing id 3 releases 1 cell; freeing it again releases nothing.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (owner per cell)O(n) per callO(n)
Optimal (free-segment list + ownership map)O(f) per allocate, O(b · f) per freeMemoryO(n)

1Brute force (owner per cell)

TimeO(n) per callEach call scans the memory array at most once.
SpaceO(n)One integer per memory cell.

Keep an array mem of length n where mem[i] is the id that owns cell i, or 0 if it is free. Allocating scans for the first run of size free cells; freeing scans the whole array and clears every cell owned by the id.

  1. allocate: walk i from 0 to n - 1, counting consecutive free cells; reset the count on an owned cell.
  2. When the count reaches size, the block starts at i - size + 1: fill those cells with mID and return the start.
  3. If the scan ends, return -1.
  4. freeMemory: set every cell equal to mID back to 0 and return how many were changed.
class Allocator {
    private final int[] mem;

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

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

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

2Optimal (free-segment list + ownership map)

TimeO(f) per allocate, O(b · f) per freeMemoryf is the number of free segments and b the number of blocks the id owns; both are usually far smaller than n, and the work no longer depends on the memory size.
SpaceO(n)Free segments plus allocated blocks, at most O(n) of them.

Instead of looking at single cells, keep the free memory as a list of free segments [start, end) sorted by start, and a map from each id to the blocks it owns. Allocation takes the first segment that is long enough and cuts the block from its front. Freeing puts each owned block back into the sorted list (found by binary search) and merges it with a neighbour segment that touches it, so the list never holds two adjacent free segments.

  1. Start with one free segment [0, n).
  2. allocate: find the first free segment with length >= size, take [start, start + size) from its front (drop the segment if it becomes empty), record the block under mID and return start; return -1 if none fits.
  3. freeMemory: remove mID's block list from the map; for each block, binary-search its position in the free list, merge with the previous segment if it ends at the block's start and with the next one if it begins at the block's end, then insert.
  4. Return the total size of the released blocks.
class Allocator {
    private final List<int[]> free = new ArrayList<>();
    private final Map<Integer, List<int[]>> owned = new HashMap<>();

    public Allocator(int n) {
        free.add(new int[] { 0, n });
    }

    public int allocate(int size, int mID) {
        for (int i = 0; i < free.size(); i++) {
            int[] seg = free.get(i);
            if (seg[1] - seg[0] >= size) {
                int start = seg[0];
                seg[0] += size;
                if (seg[0] == seg[1]) free.remove(i);
                owned.computeIfAbsent(mID, k -> new ArrayList<>()).add(new int[] { start, start + size });
                return start;
            }
        }
        return -1;
    }

    public int freeMemory(int mID) {
        List<int[]> blocks = owned.remove(mID);
        if (blocks == null) return 0;
        int total = 0;
        for (int[] b : blocks) {
            total += b[1] - b[0];
            release(b[0], b[1]);
        }
        return total;
    }

    private void release(int s, int e) {
        int lo = 0, hi = free.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (free.get(mid)[0] < s) lo = mid + 1;
            else hi = mid;
        }
        if (lo > 0 && free.get(lo - 1)[1] == s) {
            s = free.get(lo - 1)[0];
            free.remove(lo - 1);
            lo--;
        }
        if (lo < free.size() && free.get(lo)[0] == e) {
            e = free.get(lo)[1];
            free.remove(lo);
        }
        free.add(lo, new int[] { s, e });
    }
}

Edge cases to test

  • A request larger than the whole memory
  • Enough free cells in total, but no single run of free cells long enough
  • One id owning several separate blocks, all released by one freeMemory call
  • Freeing an id that owns nothing returns 0

Hints

Hint 1

With n at most 1000, simply storing the owner of every cell is enough to pass.

Hint 2

To allocate, walk the cells left to right while counting the current run of free cells; the first run that reaches size is your answer.

Hint 3

For a faster version, keep the free space as a sorted list of free segments and remember which blocks each id owns, merging neighbouring segments when memory is released.

FAQ

What is the best time complexity for Design Memory Allocator?

Optimal (free-segment list + ownership map) runs in O(f) per allocate, O(b · f) per freeMemory time and O(n) extra space. f is the number of free segments and b the number of blocks the id owns; both are usually far smaller than n, and the work no longer depends on the memory size.

Which pattern does Design Memory Allocator use?

It is a design data structures problem that uses the simulation pattern.

Is there a brute force solution for Design Memory Allocator?

Yes. Brute force (owner per cell) takes O(n) per call time and O(n) space. Keep an array mem of length n where mem[i] is the id that owns cell i, or 0 if it is free.

Which edge cases should I test for Design Memory Allocator?

A request larger than the whole memory; Enough free cells in total, but no single run of free cells long enough; One id owning several separate blocks, all released by one freeMemory call; Freeing an id that owns nothing returns 0.