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 and refine your code.

LeetCode 2502: Design Memory Allocator Solution

LeetCode 2502 Solution 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.

LeetCode 2502 Solutions in Java, C++, Python

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();
    }
}

Interactive Code Editor for LeetCode 2502

Improve Your LeetCode 2502 Solution

Use the editor below to refine the provided solution for LeetCode 2502. Select a programming language and try the following:

Add import statements if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Loading editor...