Design Memory Allocator: Contiguous Block Allocation

Design Memory Allocator is LeetCode 2502. You are given a memory array of size n where every unit starts free. You need to support two operations: allocate a contiguous block of a given size (returning the leftmost valid position), and free all units that belong to a given ID.

The problem

Implement the Allocator class:

• Allocator(int n) initializes a memory array of size n. All units start free.
• int allocate(int size, int mID) finds the leftmost block of size consecutive free memory units, assigns them all to mID, and returns the starting index. If no such block exists, return -1.
• int freeMemory(int mID) frees every memory unit with the given mID and returns how many units were freed.

Multiple blocks can be allocated to the same mID, and freeing should clear all of them at once.

The approach

The simplest representation is a flat array of size n. Each cell holds either 0 (free) or an mID (allocated).

Allocate: scan left to right, counting consecutive free cells. Every time you hit an occupied cell, reset the counter. When the counter reaches the requested size, you have found the leftmost valid block. Fill those cells with the mID and return the starting index. If you reach the end of the array without hitting the target count, return -1.

Free: scan the entire array. Every cell that matches the target mID gets set back to 0. Count how many cells you cleared and return that count.

That is the entire algorithm. No fancy data structures, no interval management. Just a linear scan for each operation.

The solution

class Allocator:
    def __init__(self, n):
        self.mem = [0] * n

    def allocate(self, size, mID):
        count = 0
        for i in range(len(self.mem)):
            if self.mem[i] == 0:
                count += 1
                if count == size:
                    start = i - size + 1
                    for j in range(start, start + size):
                        self.mem[j] = mID
                    return start
            else:
                count = 0
        return -1

    def freeMemory(self, mID):
        freed = 0
        for i in range(len(self.mem)):
            if self.mem[i] == mID:
                self.mem[i] = 0
                freed += 1
        return freed

Visual walkthrough

Let's trace through the key operations on a 10-cell array. Watch how the allocator always scans from the left, and how free clears every matching cell regardless of position.

Why leftmost matters

The problem specifies the leftmost block of consecutive free memory. This is the classic "first-fit" allocation strategy. You scan from index 0 every time, and you take the first block that is large enough.

This means you cannot skip ahead or cache the last position. Even after freeing memory in the middle of the array, the next allocate call must start scanning from 0 again, because a newly freed region might be further left than where you left off.

First-fit is simple to implement, but it does have a downside: it tends to create fragmentation at the beginning of the array. For this problem, that does not matter since the constraints are small. But in real operating systems, this is exactly why memory allocators use more sophisticated strategies like best-fit or buddy allocation.

Why brute force works here

Both n and the number of calls are at most 1000. Each allocate or freeMemory call scans at most n cells. That gives a worst case of 1000 calls times 1000 cells, or about one million operations total. That is well within time limits.

For larger constraints, you could maintain a sorted set of free intervals or use an interval tree to find and split free blocks in O(log n) time. But those approaches add significant complexity, and the problem does not require them. When the constraints are small, pick the simplest correct solution.

Complexity analysis

Time: both operations scan the array once, so each call is O(n).

Space: the memory array itself is O(n). No additional data structures are used.

Building blocks

This problem exercises two fundamental patterns:

Array simulation. The memory is modeled directly as an array. Each index represents one unit, and the value at that index represents its state. This is the same idea behind problems like Game of Life, Set Matrix Zeroes, and any problem where you simulate a process on a grid or linear structure.

First-fit allocation. Scanning left to right for the first valid position is a pattern that shows up in interval scheduling, bin packing, and operating system design. The key mechanic is maintaining a running counter of consecutive elements that meet your criteria, and resetting it when the streak breaks.

Edge cases

• No space available. If the array has no block of the requested size, allocate returns -1. Your consecutive counter will never reach the target.
• Free an mID that does not exist. No cells match, so the loop does nothing and returns 0. No special handling needed.
• Allocate fills the entire array. If n is 10 and you allocate(10, 5), every cell gets filled. Subsequent allocations return -1 until something is freed.
• Multiple blocks with the same mID. You can call allocate(2, 1) and then allocate(3, 1). Both blocks get mID 1 in different locations. When you call freeMemory(1), all five cells are cleared. The free operation does not care about contiguity.

From understanding to recall

This problem looks simple once you see the approach, and it is. But that is exactly what makes it tricky to retain. A month from now, will you remember to reset the consecutive counter when you hit an occupied cell? Will you remember to scan from the beginning every time, not from where you left off?

The gap between understanding a solution and being able to reproduce it under pressure is real. Spaced repetition closes that gap. You type the solution from scratch, and the system schedules your next review right before you would forget it. After a few reps, the scan-count-fill pattern becomes automatic.

Related posts

• LRU Cache - Another design problem that simulates a data structure with specific eviction rules
• Implement Trie - A design problem focused on building a tree structure to support prefix operations

---

New to algorithms? Understand why O(n) per call is acceptable here with our Big O Notation Guide.