# Design Memory Allocator
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-memory-allocator)
Canonical: https://scaleengineer.com/dsa/problems/design-memory-allocator
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Hash Table
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Rubrik](https://scaleengineer.com/companies/rubrik), [Two Sigma](https://scaleengineer.com/companies/two-sigma), [OpenAI](https://scaleengineer.com/companies/openai)
---
## 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:

1. **Allocate** a block of `size` consecutive free memory units and assign it the id `mID`.
2. **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.

**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**
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`.

# Approaches
## Naive Simulation with Nested Loops
This is the most straightforward brute-force approach. It uses an array to represent memory and performs linear scans for both allocation and freeing. Allocation involves a nested loop to find a contiguous free block, which is inefficient.
**Time:** - **`allocate(size, mID)`**: O(n * size). In the worst-case scenario (e.g., memory is `[1, 0, 1, 0, ...]` and we search for `size=2`), the outer loop iterates up to `n` times, and the inner loop runs `size` times for each outer iteration.
- **`freeMemory(mID)`**: O(n). We must scan the entire memory array to find all units associated with the given `mID`. · **Space:** O(n) - We only need an array of size `n` to store the state of the memory.
**Pros:** Simple to understand and implement.; Uses minimal space, just the memory array itself.
**Cons:** `allocate` operation is very slow due to the nested loop structure, making it likely to exceed time limits for larger inputs.
### Explanation
A simple integer array `memory` of size `n` is used. A value of `0` indicates a free unit, while a non-zero value represents the `mID` of the occupying block.

- **`allocate(size, mID)`**: To find the leftmost free block, we iterate from the first possible start index `i = 0` up to `n - size`. For each `i`, a second loop checks if the block of memory from `i` to `i + size - 1` is entirely free. If it is, we've found our spot. We then fill this block with the given `mID` and return the start index `i`. If the outer loop finishes without success, it means no suitable block exists, and we return -1.

- **`freeMemory(mID)`**: This operation requires a full scan of the `memory` array. We iterate from `0` to `n-1`, and for each unit `memory[i]` that matches the `mID`, we reset it to `0` and count it. The total count of freed units is returned.

```java
class Allocator {
    private int[] memory;
    private int n;

    public Allocator(int n) {
        this.n = n;
        this.memory = new int[n];
    }

    public int allocate(int size, int mID) {
        for (int i = 0; i <= n - size; i++) {
            boolean isFree = true;
            for (int j = 0; j < size; j++) {
                if (memory[i + j] != 0) {
                    isFree = false;
                    i = i + j; // Optimization to jump past the occupied block
                    break;
                }
            }
            if (isFree) {
                for (int j = i; j < i + size; j++) {
                    memory[j] = mID;
                }
                return i;
            }
        }
        return -1;
    }

    public int freeMemory(int mID) {
        int freedCount = 0;
        for (int i = 0; i < n; i++) {
            if (memory[i] == mID) {
                memory[i] = 0;
                freedCount++;
            }
        }
        return freedCount;
    }
}
```
### Algorithm
- **`Allocator(n)`**:
    1. Initialize an integer array `memory` of size `n` with all zeros.
- **`allocate(size, mID)`**:
    1. Iterate with an index `i` from `0` to `n - size`.
    2. For each `i`, assume a block is found (`isBlockFree = true`).
    3. Start a nested loop with an index `j` from `i` to `i + size - 1`.
    4. If `memory[j]` is not `0`, set `isBlockFree = false` and break the inner loop.
    5. If the inner loop completes and `isBlockFree` is still true:
        a. Fill `memory[i]` to `memory[i + size - 1]` with `mID`.
        b. Return `i`.
    6. If the outer loop completes without finding a suitable block, return `-1`.
- **`freeMemory(mID)`**:
    1. Initialize `freedCount = 0`.
    2. Iterate with an index `i` from `0` to `n - 1`.
    3. If `memory[i] == mID`:
        a. Set `memory[i] = 0`.
        b. Increment `freedCount`.
    4. Return `freedCount`.

## Optimized Linear Scan
This approach improves upon the naive simulation by optimizing the search for a free block. Instead of re-scanning for each potential starting position, it uses a single pass with a counter to find a contiguous free block of the required size.
**Time:** - **`allocate(size, mID)`**: O(n). The single pass to find a free block takes O(n), and filling the block takes O(size). The total complexity is O(n + size) = O(n).
- **`freeMemory(mID)`**: O(n). A full scan of the memory array is still necessary. · **Space:** O(n) - Space is dominated by the `memory` array.
**Pros:** The `allocate` operation is significantly faster (O(n)) than the naive approach.; The implementation remains relatively simple and easy to reason about.
**Cons:** `freeMemory` still requires a full O(n) scan of the memory, which can be slow if `n` is large and only a few units need to be freed.
### Explanation
This method still relies on a single integer array `memory` of size `n` to represent the memory state.

- **`allocate(size, mID)`**: We perform a single linear scan through the `memory` array. A counter, `consecutiveFree`, tracks the length of the current contiguous sequence of free units. When we encounter a free unit (`memory[i] == 0`), we increment the counter. If we see an occupied unit, the counter is reset to zero. As soon as `consecutiveFree` reaches the desired `size`, we have found our block. The starting index of this block is `i - size + 1`. We then fill the block with `mID` and return the start index. If we traverse the whole array without the counter reaching `size`, no such block exists.

- **`freeMemory(mID)`**: This operation is identical to the naive approach. We scan the entire array, free any units matching `mID`, and count them.

```java
class Allocator {
    private int[] memory;
    private int n;

    public Allocator(int n) {
        this.n = n;
        this.memory = new int[n];
    }

    public int allocate(int size, int mID) {
        int consecutiveFree = 0;
        for (int i = 0; i < n; i++) {
            if (memory[i] == 0) {
                consecutiveFree++;
            } else {
                consecutiveFree = 0;
            }
            if (consecutiveFree == size) {
                int start = i - size + 1;
                for (int j = 0; j < size; j++) {
                    memory[start + j] = mID;
                }
                return start;
            }
        }
        return -1;
    }

    public int freeMemory(int mID) {
        int freedCount = 0;
        for (int i = 0; i < n; i++) {
            if (memory[i] == mID) {
                memory[i] = 0;
                freedCount++;
            }
        }
        return freedCount;
    }
}
```
### Algorithm
- **`Allocator(n)`**:
    1. Initialize an integer array `memory` of size `n` with all zeros.
- **`allocate(size, mID)`**:
    1. Initialize a counter `consecutiveFree = 0`.
    2. Iterate through the `memory` array with index `i` from `0` to `n - 1`.
    3. If `memory[i]` is `0`, increment `consecutiveFree`. Otherwise, reset `consecutiveFree` to `0`.
    4. If `consecutiveFree` becomes equal to `size`:
        a. Calculate the start index: `start = i - size + 1`.
        b. Fill the block from `start` to `i` with `mID`.
        c. Return `start`.
    5. If the loop finishes without finding a block, return `-1`.
- **`freeMemory(mID)`**:
    1. Initialize `freedCount = 0`.
    2. Iterate through the `memory` array from `0` to `n - 1`.
    3. If `memory[i] == mID`, set `memory[i] = 0` and increment `freedCount`.
    4. Return `freedCount`.

## Using TreeMap for Free Blocks and HashMap for Allocations
This is a highly optimized approach that avoids linear scans of the entire memory array. It uses a `TreeMap` to keep track of free memory blocks, allowing for efficient searching and updating. A `HashMap` is used to track which blocks are allocated to which `mID`, enabling fast freeing operations.
**Time:** - **`allocate(size, mID)`**: O(f + size), where `f` is the number of free blocks. In the worst case, `f` can be O(n), so the complexity is O(n).
- **`freeMemory(mID)`**: O(b_m * log(f) + total_freed_size), where `b_m` is the number of blocks for the given `mID`, `f` is the number of free blocks, and `total_freed_size` is the sum of sizes of all freed blocks. The logarithmic factor comes from `TreeMap` operations. · **Space:** O(n + q) - `memory` array takes O(n). `freeBlocks` can have up to O(n) entries in a heavily fragmented scenario. `mIDToBlocks` can have up to `q` entries, where `q` is the number of calls.
**Pros:** Most efficient approach, especially for scenarios with high memory fragmentation.; Avoids costly full scans of memory for both `allocate` and `freeMemory` operations.
**Cons:** More complex to implement, particularly the logic for merging free blocks.; Higher constant factor overhead due to the use of complex data structures like `TreeMap` and `HashMap`.
### Explanation
This approach uses specialized data structures to manage memory efficiently.

- **Data Structures**:
    1. `TreeMap<Integer, Integer> freeBlocks`: Maps the starting index of a free block to its size. A `TreeMap` keeps keys (start indices) sorted, which helps find the leftmost block quickly and allows for efficient searching of adjacent blocks for merging.
    2. `HashMap<Integer, List<int[]>> mIDToBlocks`: Maps an `mID` to a list of its allocated blocks, where each block is `[startIndex, size]`.
    3. `int[] memory`: The underlying memory array, used for direct manipulation.

- **`allocate(size, mID)`**: We iterate through the `freeBlocks` TreeMap. Since it's sorted by start index, the first entry `(start, freeSize)` with `freeSize >= size` is the leftmost available block. We update `freeBlocks` by removing/resizing this block, update `mIDToBlocks` with the new allocation, and fill the `memory` array.

- **`freeMemory(mID)`**: We use `mIDToBlocks` to get all blocks for the given `mID`. For each block, we free it and then add it back to `freeBlocks`. The crucial step is to merge this newly freed block with any adjacent free blocks to prevent fragmentation of the free space representation. This is done by checking for a free block ending just before our new block and one starting just after.

```java
import java.util.*;

class Allocator {
    private int[] memory;
    private int n;
    private Map<Integer, List<int[]>> mIDToBlocks;
    private TreeMap<Integer, Integer> freeBlocks;

    public Allocator(int n) {
        this.n = n;
        this.memory = new int[n];
        this.mIDToBlocks = new HashMap<>();
        this.freeBlocks = new TreeMap<>();
        this.freeBlocks.put(0, n);
    }

    public int allocate(int size, int mID) {
        Integer start = -1;
        Integer freeSize = -1;
        
        for (Map.Entry<Integer, Integer> entry : freeBlocks.entrySet()) {
            if (entry.getValue() >= size) {
                start = entry.getKey();
                freeSize = entry.getValue();
                break;
            }
        }

        if (start == -1) {
            return -1;
        }

        for (int i = start; i < start + size; i++) {
            memory[i] = mID;
        }

        freeBlocks.remove(start);
        if (freeSize > size) {
            freeBlocks.put(start + size, freeSize - size);
        }

        mIDToBlocks.computeIfAbsent(mID, k -> new ArrayList<>()).add(new int[]{start, size});

        return start;
    }

    public int freeMemory(int mID) {
        if (!mIDToBlocks.containsKey(mID)) {
            return 0;
        }

        List<int[]> blocksToFree = mIDToBlocks.remove(mID);
        int totalFreed = 0;

        for (int[] block : blocksToFree) {
            int start = block[0];
            int size = block[1];
            totalFreed += size;

            for (int i = start; i < start + size; i++) {
                memory[i] = 0;
            }

            int currentStart = start;
            int currentSize = size;

            Map.Entry<Integer, Integer> prevBlock = freeBlocks.floorEntry(start - 1);
            if (prevBlock != null && prevBlock.getKey() + prevBlock.getValue() == start) {
                currentStart = prevBlock.getKey();
                currentSize += prevBlock.getValue();
                freeBlocks.remove(prevBlock.getKey());
            }

            Integer nextBlockStart = currentStart + currentSize;
            if (freeBlocks.containsKey(nextBlockStart)) {
                currentSize += freeBlocks.get(nextBlockStart);
                freeBlocks.remove(nextBlockStart);
            }
            
            freeBlocks.put(currentStart, currentSize);
        }

        return totalFreed;
    }
}
```
### Algorithm
- **`Allocator(n)`**:
    1. Initialize `memory` array, `mIDToBlocks` HashMap, and `freeBlocks` TreeMap.
    2. Add an initial entry to `freeBlocks`: `{0, n}` representing the entire memory as free.
- **`allocate(size, mID)`**:
    1. Iterate through the `freeBlocks` TreeMap to find the first entry `(start, freeSize)` where `freeSize >= size`.
    2. If found:
        a. Remove the entry from `freeBlocks`.
        b. If `freeSize > size`, add a new entry for the remaining part: `{start + size, freeSize - size}`.
        c. Add the new allocated block `{start, size}` to the list for `mID` in `mIDToBlocks`.
        d. Fill the corresponding segment in the `memory` array with `mID`.
        e. Return `start`.
    3. If no such block is found, return `-1`.
- **`freeMemory(mID)`**:
    1. Look up `mID` in `mIDToBlocks`. If not found, return 0.
    2. For each block `{start, size}` to be freed:
        a. Add `size` to a `totalFreed` counter.
        b. Clear the corresponding segment in the `memory` array.
        c. Merge the newly freed block `{start, size}` with any adjacent free blocks in `freeBlocks` by checking `floorEntry(start - 1)` and `get(start + size)`.
    3. Remove the `mID` entry from `mIDToBlocks`.
    4. Return `totalFreed`.

# Solutions
### Java

```java
class Allocator { private int [] m ; public Allocator ( int n ) { m = new int [ n ]; } public int allocate ( int size , int mID ) { int cnt = 0 ; for ( int i = 0 ; i < m . length ; ++ i ) { if ( m [ i ] > 0 ) { cnt = 0 ; } else if (++ cnt == size ) { Arrays . fill ( m , i - size + 1 , i + 1 , mID ); return i - size + 1 ; } } return - 1 ; } public int free ( int mID ) { int ans = 0 ; for ( int i = 0 ; i < m . length ; ++ i ) { if ( m [ i ] == mID ) { m [ i ] = 0 ; ++ ans ; } } return ans ; } } /** * Your Allocator object will be instantiated and called as such: * Allocator obj = new Allocator(n); * int param_1 = obj.allocate(size,mID); * int param_2 = obj.free(mID); */
```

### CPP

```cpp
class Allocator { public: Allocator ( int n ) { m = vector < int > ( n ); } int allocate ( int size , int mID ) { int cnt = 0 ; for ( int i = 0 ; i < m . size (); ++ i ) { if ( m [ i ]) { cnt = 0 ; } else if ( ++ cnt == size ) { fill ( i - size + 1 , i + 1 , mID ); return i - size + 1 ; } } return - 1 ; } int free ( int mID ) { int ans = 0 ; for ( int i = 0 ; i < m . size (); ++ i ) { if ( m [ i ] == mID ) { m [ i ] = 0 ; ++ ans ; } } return ans ; } private: vector < int > m ; void fill ( int from , int to , int val ) { for ( int i = from ; i < to ; ++ i ) { m [ i ] = val ; } } }; /** * Your Allocator object will be instantiated and called as such: * Allocator* obj = new Allocator(n); * int param_1 = obj->allocate(size,mID); * int param_2 = obj->free(mID); */
```

### Python

```python
class Allocator : def __init__ ( self , n : int ): self . m = [ 0 ] * n def allocate ( self , size : int , mID : int ) -> int : cnt = 0 for i , v in enumerate ( self . m ): if v : cnt = 0 else : cnt += 1 if cnt == size : self . m [ i - size + 1 : i + 1 ] = [ mID ] * size return i - size + 1 return - 1 def free ( self , mID : int ) -> int : ans = 0 for i , v in enumerate ( self . m ): if v == mID : self . m [ i ] = 0 ans += 1 return ans # Your Allocator object will be instantiated and called as such: # obj = Allocator(n) # param_1 = obj.allocate(size,mID) # param_2 = obj.free(mID)
```