LeetCode Problem 2349

Difficulty: 🟡 Medium
Topics: Hash Table, Design, Heap (Priority Queue), Ordered Set

Solution

LeetCode 2349 - Design a Number Container System

Problem Understanding

The problem asks us to design a data structure that supports two operations efficiently:

1. Assign a number to a given index.
2. Find the smallest index currently assigned to a given number.

The important detail is that the change(index, number) operation can both insert and replace values. If an index already contains a number, the old number is overwritten.

The find(number) operation must return the minimum index currently mapped to that number. If no index contains that number, we return -1.

Conceptually, we are maintaining a dynamic mapping like this:

index -> number

But the query operation works in the reverse direction:

number -> smallest index

That means a one-way mapping alone is not enough. We need a way to efficiently answer reverse lookups.

The constraints are important:

• Up to 10^5 operations total
• Index and number values can be as large as 10^9

The large value range tells us we cannot use arrays indexed directly by value. We need hash-based structures such as dictionaries or maps.

The operation count also tells us that an O(n) scan for every find() would become too slow in the worst case. We need operations that are close to logarithmic or constant time.

Several edge cases are important:

• Calling find() for a number that does not exist
• Replacing an existing index with a different number
• Reassigning the same number to the same index
• Multiple indices sharing the same number
• Removing the smallest index of a number due to replacement

A naive implementation can easily leave stale data behind, especially after replacements.

Approaches

Brute Force Approach

A straightforward solution is to maintain only a hash map from index to number.

indexToNumber[index] = number

When we call change(index, number), we simply update the mapping.

When we call find(number), we iterate through every stored index and check which indices currently contain the requested number. Among those matches, we return the smallest index.

This works correctly because we examine the entire state each time and therefore never miss a valid index.

However, the performance is poor. If there are n stored indices, then each find() operation costs O(n) time. With up to 10^5 operations, this can become quadratic in the worst case.

Optimal Approach

The key observation is that find(number) always asks for the smallest index associated with a number.

This naturally suggests using a min-heap for each number.

We maintain:

1. A hash map from index to current number
2. A hash map from number to a min-heap of indices

When we assign an index to a number, we push that index into the heap for the number.

The challenge is handling replacements.

Suppose index 1 previously contained 10, and now we change it to 20. The heap for 10 still contains index 1. Removing arbitrary elements from a heap efficiently is difficult.

Instead of removing immediately, we use lazy deletion.

During find(number), we repeatedly check the top index of the heap. If that index no longer maps to the requested number, it is stale, so we pop it. Eventually, the heap top becomes valid, or the heap becomes empty.

This gives efficient operations while avoiding expensive heap removals.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per find	O(n)	Scan all indices to locate smallest match
Optimal	O(log n) amortized	O(n)	Uses hash maps and heaps with lazy deletion

Algorithm Walkthrough

1. Create a hash map called index_to_number.

This stores the current number assigned to each index.

index_to_number[index] = number

2. Create another hash map called number_to_heap.

Each number maps to a min-heap containing all indices that have ever been assigned to that number.

number_to_heap[number] = min-heap of indices

3. For change(index, number):

• Update index_to_number[index] = number
• Push the index into the heap for that number

We do not attempt to remove the index from any old heap because heap removal is expensive. 4. For find(number):

• Look at the heap for the requested number

• While the heap is not empty:

• Check the smallest index at the top

• If index_to_number[top] == number, this index is valid, so return it

• Otherwise, the index is stale because it was reassigned later, so pop it

5. If the heap becomes empty, return -1.

Why it works

The heap for each number always contains every index ever assigned to that number, including stale entries. The index_to_number map stores the true current state.

During find(number), we discard stale heap entries until the heap top represents a valid current assignment. Because heaps always expose the minimum element first, the first valid index encountered must be the smallest valid index for that number.

This invariant guarantees correctness.

Python Solution

from collections import defaultdict
from heapq import heappush, heappop
from typing import Dict, List

class NumberContainers:

    def __init__(self):
        self.index_to_number: Dict[int, int] = {}
        self.number_to_heap: Dict[int, List[int]] = defaultdict(list)

    def change(self, index: int, number: int) -> None:
        self.index_to_number[index] = number
        heappush(self.number_to_heap[number], index)

    def find(self, number: int) -> int:
        heap = self.number_to_heap[number]

        while heap:
            smallest_index = heap[0]

            if self.index_to_number.get(smallest_index) == number:
                return smallest_index

            heappop(heap)

        return -1

# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index, number)
# param_2 = obj.find(number)

The implementation uses two dictionaries exactly as described in the algorithm.

The index_to_number dictionary stores the latest value assigned to each index. This represents the authoritative state of the system.

The number_to_heap dictionary maps each number to a min-heap of candidate indices. We use defaultdict(list) so heaps are created automatically when needed.

In change(), we overwrite the current mapping and push the index into the heap associated with the number.

In find(), we repeatedly inspect the heap top. If the top index still maps to the requested number, it is valid and immediately returned. Otherwise, it is stale and removed.

The lazy deletion strategy is the key optimization that keeps operations efficient.

Go Solution

package main

import (
	"container/heap"
)

type IntHeap []int

func (h IntHeap) Len() int {
	return len(h)
}

func (h IntHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	value := old[n-1]
	*h = old[:n-1]
	return value
}

type NumberContainers struct {
	indexToNumber map[int]int
	numberToHeap  map[int]*IntHeap
}

func Constructor() NumberContainers {
	return NumberContainers{
		indexToNumber: make(map[int]int),
		numberToHeap:  make(map[int]*IntHeap),
	}
}

func (this *NumberContainers) Change(index int, number int) {
	this.indexToNumber[index] = number

	if _, exists := this.numberToHeap[number]; !exists {
		h := &IntHeap{}
		heap.Init(h)
		this.numberToHeap[number] = h
	}

	heap.Push(this.numberToHeap[number], index)
}

func (this *NumberContainers) Find(number int) int {
	h, exists := this.numberToHeap[number]

	if !exists {
		return -1
	}

	for h.Len() > 0 {
		smallestIndex := (*h)[0]

		if this.indexToNumber[smallestIndex] == number {
			return smallestIndex
		}

		heap.Pop(h)
	}

	return -1
}

/**
 * Your NumberContainers object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Change(index, number);
 * param_2 := obj.Find(number);
 */

The Go version follows the same overall design but requires explicit heap implementation using the container/heap package.

Unlike Python's built-in heapq, Go requires defining methods such as Len, Less, Swap, Push, and Pop.

The Go implementation stores heap pointers inside the map so heap operations modify the original heap directly.

Go maps return zero values for missing keys, so we explicitly check whether a heap exists before accessing it.

Worked Examples

Example 1

Input:

["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]

Step-by-step Trace

Operation	index_to_number	number_to_heap	Result
find(10)	{}	{}	-1
change(2, 10)	{2: 10}	10 -> [2]
change(1, 10)	{2: 10, 1: 10}	10 -> [1, 2]
change(3, 10)	{2: 10, 1: 10, 3: 10}	10 -> [1, 2, 3]
change(5, 10)	{2: 10, 1: 10, 3: 10, 5: 10}	10 -> [1, 2, 3, 5]
find(10)	unchanged	heap top is 1	1
change(1, 20)	{2: 10, 1: 20, 3: 10, 5: 10}	10 -> [1,2,3,5], 20 -> [1]
find(10)	unchanged	top 1 is stale, pop it
continue find(10)	unchanged	new top is 2	2

The important moment occurs after change(1, 20).

The heap for 10 still contains index 1, but it is now stale because the current mapping says 1 -> 20.

The lazy deletion logic removes it during find(10).

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n) amortized	Heap insertions and removals take logarithmic time
Space	O(n)	Maps and heaps store at most all operations

Each change() operation performs a heap insertion, which costs O(log n).

Each stale heap entry is removed at most once across all future find() operations. Because of this amortized behavior, the total cost remains efficient over all operations.

The space complexity is linear because we store mappings and heap entries proportional to the number of operations.

Test Cases

# Provided example
nc = NumberContainers()
assert nc.find(10) == -1  # number does not exist yet

nc.change(2, 10)
nc.change(1, 10)
nc.change(3, 10)
nc.change(5, 10)

assert nc.find(10) == 1  # smallest valid index

nc.change(1, 20)

assert nc.find(10) == 2  # stale entry removed lazily

# Single insertion
nc = NumberContainers()
nc.change(100, 7)

assert nc.find(7) == 100  # only one index exists

# Replacing same index with different numbers
nc = NumberContainers()
nc.change(1, 5)
nc.change(1, 10)

assert nc.find(5) == -1  # old value removed logically
assert nc.find(10) == 1  # new value exists

# Multiple indices with same number
nc = NumberContainers()
nc.change(10, 3)
nc.change(5, 3)
nc.change(20, 3)

assert nc.find(3) == 5  # smallest index returned

# Reassigning same value to same index
nc = NumberContainers()
nc.change(4, 8)
nc.change(4, 8)

assert nc.find(8) == 4  # duplicate heap entries handled safely

# Large index values
nc = NumberContainers()
nc.change(10**9, 42)

assert nc.find(42) == 10**9  # supports large indices

# Removing smallest index
nc = NumberContainers()
nc.change(1, 9)
nc.change(2, 9)
nc.change(1, 8)

assert nc.find(9) == 2  # smallest valid index updated

# Number never inserted
nc = NumberContainers()

assert nc.find(999) == -1  # completely missing number

Test Summary

Test	Why
Provided example	Verifies core functionality and lazy deletion
Single insertion	Tests simplest valid state
Replace same index	Ensures reassignment works correctly
Multiple indices	Verifies smallest index selection
Duplicate assignment	Tests repeated insertions of same pair
Large values	Confirms hash-based storage handles big integers
Remove smallest index	Validates stale heap cleanup
Missing number	Ensures correct -1 behavior

Edge Cases

One important edge case occurs when an index is reassigned to a different number. This creates stale entries inside the old number's heap. A naive heap implementation might incorrectly return outdated indices. The lazy deletion strategy prevents this by validating the heap top against the authoritative index_to_number map before returning it.

Another important edge case is assigning the same number to the same index multiple times. This creates duplicate entries in the heap. The implementation still works correctly because all duplicates point to the same valid mapping. Even though redundant heap entries exist, correctness is preserved.

A third important edge case is calling find() on a number that has never been inserted. Without careful handling, this could produce key errors or invalid heap access. The implementation safely handles missing entries by returning -1.

A subtle case occurs when the smallest valid index becomes stale after reassignment. For example, if indices [1, 2, 3] belong to number 10 and index 1 changes to 20, the heap for 10 still contains 1. During find(10), the algorithm removes stale entries until it reaches the next valid smallest index, which is 2.