Problem Description

This problem asks you to implement a basic HashMap data structure from scratch without using any built-in hash table libraries.

A HashMap is a data structure that stores key-value pairs and provides fast access to values based on their keys. You need to create a class called MyHashMap with the following functionality:

1. Constructor (MyHashMap()): Creates an empty HashMap when initialized.

2. Put operation (put(key, value)): Stores a key-value pair in the HashMap. If the key already exists, the method should update its value with the new one provided.

3. Get operation (get(key)): Retrieves the value associated with a given key. If the key doesn't exist in the HashMap, it should return -1.

4. Remove operation (remove(key)): Deletes a key and its associated value from the HashMap if the key exists.

The solution shown uses a direct addressing approach with an array of size 1,000,001. This approach works because the problem constraints guarantee that keys will be in the range [0, 10^6]. Each index in the array represents a possible key, and the value at that index represents the corresponding value in the HashMap. The implementation initializes all positions to -1 to indicate empty slots. When put is called, it directly assigns the value to data[key]. The get operation simply returns data[key], and remove sets data[key] back to -1.

While this solution is simple and provides O(1) time complexity for all operations, it uses O(10^6) space regardless of how many elements are actually stored, making it space-inefficient for sparse data.

Intuition

The key insight for solving this problem is recognizing that we need a way to map keys to values with fast access times. Since we're not allowed to use built-in hash tables, we need to think about the fundamental principle behind how hash maps work.

At its core, a hash map uses an array where we can directly access any position using an index. The challenge is usually converting arbitrary keys into array indices. However, when we look at the problem constraints, we notice that keys are limited to the range [0, 10^6]. This is a crucial observation.

Since the keys are already integers within a fixed range, we can use them directly as array indices without any hashing function. This eliminates the complexity of dealing with hash collisions and designing hash functions. We can simply create an array large enough to accommodate all possible keys.

The thought process goes like this:

• We need O(1) access time for put, get, and remove operations
• Arrays provide O(1) access time when we know the index
• Our keys are integers from 0 to 1,000,000
• We can use the key itself as the array index

For handling the "empty" state (when a key doesn't exist), we need a sentinel value. Since the problem specifies returning -1 for non-existent keys, we can initialize our entire array with -1. This way, any unset position naturally returns the correct value for get operations.

This direct addressing approach trades space for simplicity and speed. While it uses more memory than necessary (especially when storing few elements), it completely avoids the complexities of collision resolution strategies like chaining or open addressing that would be needed in a more space-efficient implementation.

Learn more about Linked List patterns.

Solution Approach

The implementation uses a direct addressing table approach with a fixed-size array. Here's how each component works:

Data Structure:

• We use a single array self.data of size 1,000,001 to store all key-value mappings
• Each index in the array represents a possible key (0 to 1,000,000)
• The value at each index represents the corresponding value for that key

Initialization (__init__):

self.data = [-1] * 1000001

• Creates an array with 1,000,001 elements, all initialized to -1
• The value -1 serves as a marker for "no value exists at this key"
• This initialization ensures that get operations on non-existent keys automatically return -1

Put Operation (put(key, value)):

self.data[key] = value

• Directly assigns the value to the array at index key
• If a value already exists at that key, it gets overwritten (update behavior)
• Time complexity: O(1) - direct array access

Get Operation (get(key)):

return self.data[key]

• Simply returns the value stored at index key
• If the key was never set, it returns -1 (the initialization value)
• Time complexity: O(1) - direct array access

Remove Operation (remove(key)):

self.data[key] = -1

• Sets the value at index key back to -1
• This effectively marks the key as "removed" or "non-existent"
• Time complexity: O(1) - direct array access

Trade-offs of this approach:

• Advantages: Extremely simple implementation, guaranteed O(1) time for all operations, no collision handling needed
• Disadvantages: Uses O(10^6) space regardless of the number of elements stored, only works when keys are integers in a known range

This solution leverages the constraint that keys are bounded integers to eliminate the need for a hash function entirely, making it a perfect example of how problem constraints can lead to simplified solutions.

Example Walkthrough

Let's walk through a sequence of operations to see how our HashMap works:

Initial State:

data = [-1, -1, -1, -1, -1, ...] (1,000,001 elements, all -1)

Operation 1: put(2, 10)

• We want to store value 10 with key 2
• We directly access data[2] and set it to 10

data = [-1, -1, 10, -1, -1, ...]
         ^    ^   ^
       key=0 key=1 key=2

Operation 2: put(5, 25)

• Store value 25 with key 5
• Set data[5] = 25

data = [-1, -1, 10, -1, -1, 25, -1, ...]
                             ^
                           key=5

Operation 3: get(2)

• Retrieve the value for key 2
• Simply return data[2], which is 10
• Returns: 10

Operation 4: get(3)

• Retrieve the value for key 3
• Return data[3], which is -1 (never set)
• Returns: -1 (indicating key doesn't exist)

Operation 5: put(2, 15)

• Update the value for key 2 from 10 to 15
• Set data[2] = 15 (overwrites the old value)

data = [-1, -1, 15, -1, -1, 25, -1, ...]
                ^
              key=2 (updated)

Operation 6: remove(5)

• Remove the key-value pair for key 5
• Set data[5] = -1 (back to "empty" state)

data = [-1, -1, 15, -1, -1, -1, -1, ...]
                             ^
                           key=5 (removed)

Operation 7: get(5)

• Try to retrieve the value for key 5 (which we just removed)
• Return data[5], which is now -1
• Returns: -1 (indicating key doesn't exist anymore)

This example demonstrates how:

• The key directly maps to the array index (no hashing needed)
• Put operations simply store values at the corresponding index
• Get operations return whatever is at that index (-1 if never set or removed)
• Remove operations reset the position to -1
• All operations take O(1) time since they're just direct array accesses

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(): O(1000001) or O(10^6) - initializes an array of size 1000001 with -1 values
• put(key, value): O(1) - direct array access and assignment at index key
• get(key): O(1) - direct array access at index key
• remove(key): O(1) - direct array access and assignment at index key

Space Complexity:

• O(1000001) or O(10^6) - the implementation uses a fixed-size array of 1000001 elements regardless of how many key-value pairs are actually stored. This is constant space with respect to the constraint that keys are in the range [0, 10^6], but represents significant memory overhead when few keys are used.

Analysis: This implementation uses a direct-address table approach where each possible key (0 to 1000000) maps directly to an array index. While this provides optimal O(1) time complexity for all operations, it trades off space efficiency by allocating memory for all possible keys upfront, even if only a small subset of keys are actually used.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Memory Inefficiency for Sparse Data

The most significant pitfall of this direct addressing approach is the massive memory waste when dealing with sparse data. Even if you only store a single key-value pair, the solution allocates memory for 1,000,001 integers.

Example scenario:

hashmap = MyHashMap()
hashmap.put(999999, 100)  # Only one element, but using ~4MB of memory

Solution: Implement a proper hash table with collision handling:

class MyHashMap:
    def __init__(self):
        self.size = 1000  # Much smaller initial size
        self.buckets = [[] for _ in range(self.size)]
  
    def _hash(self, key):
        return key % self.size
  
    def put(self, key: int, value: int) -> None:
        hash_key = self._hash(key)
        bucket = self.buckets[hash_key]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
  
    def get(self, key: int) -> int:
        hash_key = self._hash(key)
        bucket = self.buckets[hash_key]
        for k, v in bucket:
            if k == key:
                return v
        return -1
  
    def remove(self, key: int) -> None:
        hash_key = self._hash(key)
        bucket = self.buckets[hash_key]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return

2. Inflexibility with Key Constraints

The current implementation breaks if keys fall outside the [0, 10^6] range, causing index out of bounds errors.

Problem example:

hashmap = MyHashMap()
hashmap.put(-1, 50)      # IndexError: list index out of range
hashmap.put(1000001, 60) # IndexError: list index out of range

Solution: Add boundary checking or use a dynamic approach:

def put(self, key: int, value: int) -> None:
    if 0 <= key <= 1000000:
        self.data[key] = value
    # Or raise an exception for invalid keys

3. Confusion with Special Value -1

Using -1 as both a sentinel value for "empty" and a potential legitimate value can cause ambiguity. If the problem allowed storing -1 as a valid value, this approach would fail.

Problematic scenario:

hashmap.put(5, -1)  # Storing -1 as a legitimate value
hashmap.remove(5)    # Also sets to -1
# Now we can't distinguish between "key 5 has value -1" vs "key 5 doesn't exist"

Solution: Use a separate data structure to track existence:

class MyHashMap:
    def __init__(self):
        self.data = [0] * 1000001
        self.exists = [False] * 1000001
  
    def put(self, key: int, value: int) -> None:
        self.data[key] = value
        self.exists[key] = True
  
    def get(self, key: int) -> int:
        if self.exists[key]:
            return self.data[key]
        return -1
  
    def remove(self, key: int) -> None:
        self.exists[key] = False