We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design a Number Container System

Difficulty: Medium

Problem Description

Design a number container system that can insert or replace a number at a given index and return the smallest index for a given number.

Key Insights

  • The system must efficiently handle updates and queries.
  • Each index can hold a number, and numbers can be replaced.
  • To find the smallest index for a given number, we need to maintain a mapping between numbers and their indices.

Space and Time Complexity

Time Complexity: O(1) for change, O(log k) for find where k is the number of indices holding the number.
Space Complexity: O(n) where n is the number of indices in the system.

Solution

We can use two hash tables (dictionaries):

  1. index_map: This maps each index to the number it holds.
  2. number_map: This maps each number to a sorted set of indices that hold that number.

When we call change(index, number), we update the index_map and also update the number_map. If the index is already occupied, we need to remove the old number from number_map.

When we call find(number), we simply fetch the sorted list of indices from number_map and return the smallest index.

Code Solutions

class NumberContainers:
    def __init__(self):
        self.index_map = {}  # Maps index to number
        self.number_map = {}  # Maps number to set of indices

    def change(self, index: int, number: int) -> None:
        if index in self.index_map:
            old_number = self.index_map[index]
            # Remove the old number from the number_map
            self.number_map[old_number].remove(index)
            if not self.number_map[old_number]:
                del self.number_map[old_number]

        # Insert or replace the number at index
        self.index_map[index] = number
        if number not in self.number_map:
            self.number_map[number] = set()
        self.number_map[number].add(index)

    def find(self, number: int) -> int:
        if number in self.number_map and self.number_map[number]:
            return min(self.number_map[number])  # Return the smallest index
        return -1  # If number is not present
← Back to All Questions