2349. Design a Number Container System

MediumView on LeetCode

Hash Table Design

Intuition

Design NumberContainers with change(index, number) and find(number). HashMap: number -> sorted set of indices.

Algorithm

1indexMap: index -> number. numMap: number -> TreeSet of indices.
2change: update indexMap, remove old from numMap, add new to numMap.
3find: return min of numMap.get(number), or -1 if empty.

Common Pitfalls

•Use TreeSet (sorted) for O(log n) min. Handle overwriting existing indices.

2349.cs

// Approach: HashMap index→number; per-number SortedSet of indices; O(log n) per operation.
// Time: O(log n) per op Space: O(n)

public class NumberContainers
{
    private Dictionary<int, int> indexToNumber = new Dictionary<int, int>();
    private Dictionary<int, SortedSet<int>> numberToIndices = new Dictionary<int, SortedSet<int>>();

    public NumberContainers()
    {

    }

    public void Change(int index, int number)
    {
        if (indexToNumber.TryGetValue(index, out int originalNumber))
        {
            if (numberToIndices.TryGetValue(originalNumber, out SortedSet<int> indices))
            {
                indices.Remove(index);
                if (indices.Count == 0)
                    numberToIndices.Remove(originalNumber);
            }
        }

        if (!numberToIndices.ContainsKey(number))
            numberToIndices[number] = new SortedSet<int>();

        numberToIndices[number].Add(index);
        indexToNumber[index] = number;
    }

    public int Find(int number)
    {
        if (numberToIndices.TryGetValue(number, out SortedSet<int> indices))
        {
            foreach (int index in indices)
                return index;
        }
        return -1;
    }
}

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

Was this solution helpful?