Design memory allocator

Array Hash Table Design Simulation

49.7% acceptance

Feb 23, 2026

357

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

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

pub struct Allocator {
  memory: Vec<i32>,
}

impl Allocator {
  pub fn new(n: i32) -> Self {
    Allocator {
      memory: vec![0; n as usize],
    }
  }

  pub fn allocate(&mut self, size: i32, m_id: i32) -> i32 {
    let size = size as usize;
    let n = self.memory.len();
    let mut i = 0;
    while i + size <= n {
      if self.memory[i..i + size].iter().all(|&x| x == 0) {
        for j in i..i + size {
          self.memory[j] = m_id;
        }
        return i as i32;
      }
      i += 1;
    }
    -1
  }

  pub fn free_memory(&mut self, m_id: i32) -> i32 {
    let mut count = 0;
    for x in &mut self.memory {
      if *x == m_id {
        *x = 0;
        count += 1;
      }
    }
    count
  }
}