Abstract / Summary

Design a class to allocate and free memory blocks of specific sizes using a list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 50% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Design
• Hash Table
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The Allocator class implements a simple contiguous memory manager using a list of tuples. Each tuple stores a start offset, a length, and an identifier (0 denotes a free region). The internal list, self.space, is always kept ordered by start address, which allows linear scans for allocation and deallocation while preserving the logical layout of the memory space.

Core Data Structure

The constructor creates a single free block that spans the whole address space:

class Allocator:
    def __init__(self, n: int):
        self.space = [(0, n, 0)]   # (start, length, ID); ID 0 means free

The tuple layout is consistent throughout the class, making it easy to reason about the state of each region.

Allocation Logic

The allocate method searches for the first free block that can satisfy the requested size. The loop extracts the tuple components and skips any block that is already allocated (id != 0) or too small (length < size). When a suitable block is found, the method performs two actions:

1. Mark the block as allocated - the tuple at the current index is replaced with a new tuple that carries the caller’s mID.
2. Split the block if it is larger than needed - the original free block is truncated to the requested size, and the remainder is inserted back into the list as a new free block.

The insertion uses insort from the bisect module, which maintains the sorted order without a full resort:

def allocate(self, size: int, mID: int) -> int:
    for i in range(len(self.space)):
        start, length, id = self.space[i]
        if id != 0 or length < size:
            continue

        # Claim the block
        self.space[i] = (start, length, mID)

        # Split if there is excess space
        if length > size:
            self.space[i] = (start, size, mID)
            insort(self.space, (start + size, length - size, 0))

        return start

    return -1

Edge Cases Handled in Allocation

• Exact fit - when length == size, the split branch is bypassed, leaving the block exactly sized for the allocation.
• Allocation at the end of the address space - the linear scan reaches the final tuple; if it matches the criteria, the method returns its start offset, even when the block is the last one.
• No suitable block - after exhausting the list, the method returns -1, signalling failure without altering the internal state.

Deallocation Logic

The free method releases all blocks belonging to a given mID. It iterates over the list, converting matching allocated blocks back to free (id = 0) and accumulating the total reclaimed size:

def free(self, mID: int) -> int:
    result = 0
    for i in range(len(self.space)):
        if i >= len(self.space):   # defensive guard for list shrinkage during merging
            break

        start, length, id = self.space[i]
        if id != mID:
            continue

        # Release the block
        result += self.space[i][1]
        self.space[i] = (start, length, 0)

After all relevant blocks are marked free, a second pass merges adjacent free regions. The merge proceeds from right to left, ensuring that deletions do not affect the indices of yet-to-process elements:

    # Merge adjacent free blocks (right-to-left)
    for i in range(len(self.space) - 1, 0, -1):
        if self.space[i][2] == self.space[i - 1][2]:   # same ID (both 0)
            self.space[i - 1] = (
                self.space[i - 1][0],
                self.space[i - 1][1] + self.space[i][1],
                self.space[i][2]
            )
            del self.space[i]

    return result

Edge Cases Handled in Deallocation

• Multiple non-contiguous blocks belonging to the same mID - the first loop frees each independently, and the subsequent merge step coalesces any that become adjacent after other frees.
• Merging across the list boundaries - the right-to-left traversal guarantees that a block merged into its left neighbor will not be revisited, preventing redundant checks.
• Self-modifying list during iteration - the guard if i >= len(self.space): break protects against index errors that could arise if a block is removed during the merge phase.

Performance Optimizations

• Sorted insertion with insort - by inserting the remainder of a split block using binary search, the code avoids a full list sort after each allocation. This keeps the list ordered with minimal overhead.
• Early exit on successful allocation - as soon as a fitting block is found, the method returns the start address, preventing unnecessary scanning of later blocks.
• Two-phase deallocation - separating the free-marking pass from the merging pass simplifies each loop and allows the merge to operate on a stable set of free blocks, reducing the number of element moves.
• Right-to-left merge direction - deleting an element while iterating forward would shift subsequent indices and require extra bookkeeping. Traversing backward eliminates that complication and ensures each merge operation is performed in constant time relative to the number of blocks merged.

The combination of these techniques yields a memory manager that remains responsive even as the number of allocated and free regions grows, while keeping the internal representation compact through aggressive coalescing of free space.

Imagine a long bookshelf that starts out completely empty. The bookshelf has many slots where toys can go. To keep things organized, there is a special box called an allocator that acts like a librarian for this shelf.

When someone asks for space for their toys, the librarian looks at the shelf. The librarian searches for an empty gap that is big enough to hold the new toys. When a good spot is found, the librarian marks that section of the shelf with a secret ID number so everyone knows who the toys belong to. If the gap on the shelf is much bigger than what is needed, the librarian splits it into two pieces. One piece is for the toys, and the other piece stays empty for someone else to use later.

When it is time to clear the shelf, the librarian looks for all the sections marked with a specific ID number. Those sections are wiped clean, which makes them empty again. Sometimes, after cleaning, there are two empty sections sitting right next to each other. When that happens, the librarian puts them together to make one big empty space instead of two tiny ones. This helps keep the shelf tidy so that later on, someone else can use that large combined space for their own toys.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python		Java		C++	TS
	WalkCCC	Python		Java		C++
	leetcode.ca	Python		Java	Go	C++	TS
	Progiez	Python		Java		C++
github	charles-wangkai			Java
	fsq					C++
	JoshCrozier		JS
	muhammadfarhankt				Go
	trung-hn	Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
muhammadfarhankt	Go
trung-hn	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality