Design a Number Container System - Practice Coding Problems

Design a Number Container System - Problem

Design a number container system that can perform the following operations:

Insert or Replace a number at the given index in the system.
Return the smallest index for the given number in the system.

Implement the NumberContainers class:

NumberContainers() Initializes the number container system.
void change(int index, int number) Fills the container at index with the number. If there is already a number at that index, replace it.
int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number in the system.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["NumberContainers", "change", "find", "change", "find", "find"], values = [[], [1, 10], [1], [2, 20], [1], [3]]

› Output: [1, 1, -1]

💡 Note: NumberContainers nc = new NumberContainers(); nc.change(1, 10); // container[1] = 10. nc.find(1) returns 1; nc.change(2, 20); // container[2] = 20. nc.find(1) returns 1; nc.find(3) returns -1 (not found).

Example 2 — Multiple Indices Same Number

$ Input: operations = ["NumberContainers", "change", "change", "find", "change", "find"], values = [[], [1, 10], [3, 10], [10], [2, 10], [10]]

› Output: [1, 1]

💡 Note: Multiple indices can have same number. System returns smallest index: indices 1 and 3 both have 10, so find(10) returns 1. After adding index 2 with 10, find(10) still returns 1 (smallest).

Example 3 — Replace Existing Value

$ Input: operations = ["NumberContainers", "change", "find", "change", "find"], values = [[], [1, 10], [10], [1, 20], [10]]

› Output: [1, -1]

💡 Note: Initially container[1] = 10, so find(10) returns 1. Then change(1, 20) replaces the value, so find(10) returns -1 (no longer exists).

Constraints

1 ≤ index, number ≤ 10⁹
At most 10⁵ calls to change and find

Visualization

Tap to expand

Understanding the Visualization

Input

Operations: change(1,10), find(1), change(2,20)

Process

Maintain index→number mapping and reverse lookup

Output

Find operations return smallest index or -1

Key Takeaway

🎯 Key Insight: Use dual hash maps - one for direct index access, another with min-heaps for efficient minimum index queries

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to maintain two hash maps: one for index→number lookups and another for number→sorted indices. The optimal approach uses min-heaps to efficiently find the smallest index for any number. Best approach: Two Hash Maps with Min-Heap. Time: O(log k) per operation, Space: O(n + m).

Common Approaches

Approach	Time	Space	Notes
✓ Two Hash Maps with Min-Heap	O(log k) change, O(log k) find	O(n + m)	Use index→number map and number→min-heap map for efficient operations
Single Map with Linear Search	O(1) change, O(n) find	O(n)	Store index→number mapping and search linearly for find operations

Two Hash Maps with Min-Heap — Algorithm Steps

Store index→number in first map
Store number→min-heap of indices in second map
For find: peek min-heap top, validate it's still current

Visualization

Tap to expand

Step-by-Step Walkthrough

Dual Mapping

Maintain index→number and number→heap

Heap Access

Get minimum index from heap in O(1)

Validation

Verify heap top is still valid

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_SIZE 1000
#define MAX_HEAP_SIZE 1000

typedef struct {
    int data[MAX_HEAP_SIZE];
    int size;
} MinHeap;

MinHeap* createMinHeap() {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->size = 0;
    return heap;
}

void heapify(MinHeap* heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    
    if (left < heap->size && heap->data[left] < heap->data[smallest])
        smallest = left;
    
    if (right < heap->size && heap->data[right] < heap->data[smallest])
        smallest = right;
    
    if (smallest != idx) {
        int temp = heap->data[idx];
        heap->data[idx] = heap->data[smallest];
        heap->data[smallest] = temp;
        heapify(heap, smallest);
    }
}

void push(MinHeap* heap, int val) {
    if (heap->size >= MAX_HEAP_SIZE) return;
    
    heap->data[heap->size] = val;
    int idx = heap->size++;
    
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (heap->data[idx] >= heap->data[parent]) break;
        int temp = heap->data[idx];
        heap->data[idx] = heap->data[parent];
        heap->data[parent] = temp;
        idx = parent;
    }
}

int pop(MinHeap* heap) {
    if (heap->size == 0) return -1;
    
    int min = heap->data[0];
    heap->data[0] = heap->data[--heap->size];
    heapify(heap, 0);
    return min;
}

int peek(MinHeap* heap) {
    return heap->size > 0 ? heap->data[0] : -1;
}

typedef struct {
    int indices[MAX_SIZE];
    int numbers[MAX_SIZE];
    int size;
    MinHeap* heaps[MAX_SIZE];
    int heapNumbers[MAX_SIZE];
    int heapCount;
} NumberContainers;

NumberContainers* numberContainersCreate() {
    NumberContainers* obj = (NumberContainers*)malloc(sizeof(NumberContainers));
    obj->size = 0;
    obj->heapCount = 0;
    return obj;
}

MinHeap* findHeap(NumberContainers* obj, int number) {
    for (int i = 0; i < obj->heapCount; i++) {
        if (obj->heapNumbers[i] == number) {
            return obj->heaps[i];
        }
    }
    return NULL;
}

void numberContainersChange(NumberContainers* obj, int index, int number) {
    for (int i = 0; i < obj->size; i++) {
        if (obj->indices[i] == index) {
            obj->numbers[i] = number;
            MinHeap* heap = findHeap(obj, number);
            if (!heap) {
                heap = createMinHeap();
                obj->heaps[obj->heapCount] = heap;
                obj->heapNumbers[obj->heapCount] = number;
                obj->heapCount++;
            }
            push(heap, index);
            return;
        }
    }
    
    obj->indices[obj->size] = index;
    obj->numbers[obj->size] = number;
    obj->size++;
    
    MinHeap* heap = findHeap(obj, number);
    if (!heap) {
        heap = createMinHeap();
        obj->heaps[obj->heapCount] = heap;
        obj->heapNumbers[obj->heapCount] = number;
        obj->heapCount++;
    }
    push(heap, index);
}

int numberContainersFind(NumberContainers* obj, int number) {
    MinHeap* heap = findHeap(obj, number);
    if (!heap || heap->size == 0) return -1;
    
    while (heap->size > 0) {
        int minIndex = peek(heap);
        
        int found = 0;
        for (int i = 0; i < obj->size; i++) {
            if (obj->indices[i] == minIndex && obj->numbers[i] == number) {
                found = 1;
                break;
            }
        }
        
        if (found) return minIndex;
        pop(heap);
    }
    
    return -1;
}

int* solution(char operations[][20], int values[][2], int operationsSize, int* returnSize) {
    NumberContainers* nc = numberContainersCreate();
    int* results = (int*)malloc(operationsSize * sizeof(int));
    int resultIndex = 0;
    
    for (int i = 0; i < operationsSize; i++) {
        if (strcmp(operations[i], "change") == 0) {
            numberContainersChange(nc, values[i][0], values[i][1]);
        } else if (strcmp(operations[i], "find") == 0) {
            results[resultIndex++] = numberContainersFind(nc, values[i][0]);
        }
    }
    
    *returnSize = resultIndex;
    return results;
}

int main() {
    char operations[][20] = {"NumberContainers", "change", "find", "change", "find", "find"};
    int values[][2] = {{0,0}, {1,10}, {1,0}, {2,20}, {1,0}, {3,0}};
    int returnSize;
    
    int* result = solution(operations, values, 6, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log k) change, O(log k) find

Heap operations for maintaining sorted indices, k is max indices per number

⚡ Linearithmic

Space Complexity

O(n + m)

Two hash maps plus heaps storing n indices total, m unique numbers

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Hash Maps with Min-Heap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler