LeetCode 2502: Design Memory Allocator Solution

Master LeetCode problem 2502 (Design Memory Allocator), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2502. Design Memory Allocator

Medium

Array Hash Table Design Simulation

Problem Explanation

Explanation:

To solve this problem, we can use a simple array to represent the memory units and keep track of which units are allocated to which mID. We can maintain a list of free blocks to efficiently allocate memory. When allocating memory, we iterate through the list of free blocks to find a suitable block. When freeing memory, we simply mark the units allocated to the given mID as free.

Algorithm:

Initialize the memory array of size n and a map to store the allocated memory units.
Initialize a list to store free blocks, initially containing one block from index 0 to n-1.
Implement the allocate method to find a suitable free block and assign it to the given mID.
Implement the freeMemory method to free all memory units assigned to the given mID.

Time Complexity:

allocate: O(n) in the worst case (when all units are allocated).
freeMemory: O(n) in the worst case (when all units are assigned to the mID being freed).

Space Complexity:

O(n) for storing the memory array and the map of allocated units.

Solution Code

class Allocator {
    int[] memory;
    Map<Integer, Set<Integer>> allocated;
    List<int[]> freeBlocks;

    public Allocator(int n) {
        memory = new int[n];
        allocated = new HashMap<>();
        freeBlocks = new ArrayList<>();
        freeBlocks.add(new int[]{0, n-1});
    }

    public int allocate(int size, int mID) {
        for (int[] block : freeBlocks) {
            if (block[1] - block[0] + 1 >= size) {
                for (int i = block[0]; i < block[0] + size; i++) {
                    memory[i] = mID;
                    allocated.computeIfAbsent(mID, k -> new HashSet<>()).add(i);
                }
                if (block[1] - block[0] + 1 == size) {
                    freeBlocks.remove(block);
                } else {
                    block[0] += size;
                }
                return block[0];
            }
        }
        return -1;
    }

    public int freeMemory(int mID) {
        if (!allocated.containsKey(mID)) return 0;
        Set<Integer> units = allocated.get(mID);
        for (int unit : units) {
            memory[unit] = 0;
        }
        freeBlocks.add(units.stream().mapToInt(Integer::intValue).toArray());
        allocated.remove(mID);
        return units.size();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2502 (Design Memory Allocator)?

This page provides optimized solutions for LeetCode problem 2502 (Design Memory Allocator) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2502 (Design Memory Allocator)?

The time complexity for LeetCode 2502 (Design Memory Allocator) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2502 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2502 in Java, C++, or Python.

Back to LeetCode Solutions