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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design a Number Container System

Number: 2434

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Design a number container system that supports two main operations:

  1. change(index, number): Insert or replace the number at the given index.
  2. find(number): Return the smallest index that contains the given number (or -1 if none exists).

Key Insights

  • We need to support dynamic updates (insertion and replacement) on indices.
  • For each number, it is required to quickly determine the minimum index that holds that number.
  • A mapping from index to current value helps in tracking replacements.
  • For each number we can maintain a heap (or an ordered set) of indices; this allows for efficient retrieval of the smallest available index.
  • When updating an index to a new value, the old value’s set must be lazily updated (or cleaned up during retrieval) since the index might still exist in the min-heap of the old value.

Space and Time Complexity

Time Complexity: O(log n) per change and find operation on average (n is the number of indices maintained). Space Complexity: O(n) in the worst-case scenario for storing mappings and heaps for each number.

Solution

We use two main data structures:

  1. A hash map (or dictionary) "indexMap" to store the current number at each index.
  2. Another hash map "numToIndices" mapping each number to a min-heap (or balanced BST/ordered set) of indices where that number occurs. When a change(index, number) call is made, we check if the index already exists. If it does, we update the indexMap and add the new index to the heap corresponding to the new number. The outdated index remains in the previous number's heap, and while performing a find operation, we perform lazy deletion: we repeatedly check the top of the heap to verify that the index still maps to the queried number in indexMap. This ensures that the find(number) returns the correct minimal index without expensive heap removal operations.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

import heapq

class NumberContainers:
    def __init__(self):
        # Dictionary to map index to its current number
        self.indexMap = {}
        # Dictionary mapping number to a min-heap of indices
        self.numToIndices = {}

    def change(self, index: int, number: int) -> None:
        # If index already exists, update it.
        # The outdated index remains in the old number's heap and will be cleaned lazily.
        if index in self.indexMap:
            oldNumber = self.indexMap[index]
        self.indexMap[index] = number
        
        # Create a new heap for this number if it does not exist
        if number not in self.numToIndices:
            self.numToIndices[number] = []
        # Push the index onto the heap for this number
        heapq.heappush(self.numToIndices[number], index)

    def find(self, number: int) -> int:
        # If the number is not present in the mapping, return -1
        if number not in self.numToIndices:
            return -1

        heap = self.numToIndices[number]
        # Clean up outdated indices via lazy deletion
        while heap and self.indexMap.get(heap[0], None) != number:
            heapq.heappop(heap)
        
        # Return the smallest valid index if exists
        return heap[0] if heap else -1
← Back to All Questions