Design Hashmap Leetcode Problem 706 [Python Solution]

Design Hashmap Leetcode problem is an Arrays & Hashing challenge with “Easy” difficulty. It’s a great introductory problem to hash maps and will help you understand the fundamental operations of a hashmap: put, get, and remove.

Let’s dive right in and break down the problem step by step.

Problem Overview

Problem Statement:

Design a HashMap without using any built-in hash table libraries.

Specification:

You are tasked with implementing the MyHashMap class with the following methods:

1. MyHashMap(): This initializes the object with an empty map.
2. put(int key, int value): Inserts a (key, value) pair into the HashMap.

If the key already exists in the map, update the corresponding value.

3. get(int key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
4. remove(int key): Removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Let’s illustrate how the MyHashMap class should work with an example:

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation:

1. We create a new MyHashMap instance.
2. We put the key-value pair (1, 1) into the hashmap.
3. We put the key-value pair (2, 2) into the hashmap.
4. We get the value associated with key 1, which is 1.
5. We get the value associated with key 3, but it doesn’t exist, so we return -1.
6. We update the value of key 2 to be 1.
7. We get the value associated with key 2, which is 1 after the update.
8. We remove the key 2 from the hashmap.
9. We attempt to get the value associated with key 2 again, but it’s been removed, so we return -1.

Constraints:

• 0 <= key, value <= 10^6
• At most 10^4 calls will be made to put, get, and remove.

That was too many ‘We(s)’, but now that we have a clear understanding of the problem, let’s proceed to discuss the implementation.

Understanding the Constraints

Before we delve into the code, let’s briefly discuss the constraints.

Understanding these constraints is crucial for optimizing our solution.

Here’s a breakdown:

• The range of key and value is from 0 to 10^6. This means our hashmap should be able to handle a wide range of key-value pairs.
• The number of operations (put, get, remove) is limited to at most 10^4 calls.

This indicates that our solution should be efficient enough to handle a large number of operations without exceeding time limits.

Now that we have a grasp of the problem and its constraints, let’s explore how to implement the MyHashMap class.

MyHashMap LeetCode Problem Solution

We will implement the MyHashMap class with the following operations: put, get, and remove.

Our solution uses the concept of chaining to handle hash collisions, which is a common approach in implementing hash maps.

Let’s start by defining the ListNode class, which will be used to create linked lists in our hash map.

Each node in the linked list will store a key, a value, and a reference to the next node.

class ListNode:
    def __init__(self, key=-1, val=-1, next=None):
        self.key = key
        self.val = val
        self.next = next

Now, let’s implement the MyHashMap class with the following components:

1. __init__: Initializes the object with an empty map (implemented as an array of linked lists).
2. hashcode: A helper method to calculate the hash code for a given key.
3. put: Inserts a (key, value) pair into the hash map.

If the key already exists in the map, it updates the corresponding value.

4. get: Returns the value associated with the specified key or -1 if the key is not found.
5. remove: Removes the key and its corresponding value from the map if it exists.

Let’s dive into the code:

class ListNode:
    def __init__(self, key=None, val=None):
        self.key = key
        self.val = val
        self.next = None

class MyHashMap:
    def __init__(self):
        # Initialize the object with an empty map (implemented as an array of linked lists).
        self.map = [ListNode() for i in range(1000)]

    def hashcode(self, key):
        # Helper method to calculate the hash code for a given key.
        return key % len(self.map)

    def put(self, key: int, value: int) -> None:
        # Inserts a (key, value) pair into the hash map. If the key already exists, it updates the corresponding value.
        index = self.hashcode(key)
        cur = self.map[index]
        while cur.next:
            if cur.next.key == key:
                cur.next.val = value
                return
            cur = cur.next
        cur.next = ListNode(key, value)

    def get(self, key: int) -> int:
        # Returns the value associated with the specified key or -1 if the key is not found.
        index = self.hashcode(key)
        cur = self.map[index].next
        while cur and cur.key != key:
            cur = cur.next
        if cur:
            return cur.val
        return -1

    def remove(self, key: int) -> None:
        # Removes the key and its corresponding value from the map if it exists.
        index = self.hashcode(key)
        cur = self.map[index]
        while cur.next and cur.next.key != key:
            cur = cur.next
        if cur and cur.next:
            cur.next = cur.next.next

This implementation uses an array of linked lists to handle hash collisions.

Each index of the array represents a bucket in which we store the linked list nodes.

The hashcode method calculates the index (bucket) for a given key using the modulo operation.

Time and Space Complexity

Let’s analyze the time and space complexity of our solution:

• Time Complexity:
• The put operation, which inserts or updates a key-value pair, has an average time complexity of O(1).

In the worst case, when many keys are mapped to the same index (hash collisions), it could be O(n), where n is the number of keys in the same index, but this is limited by the problem’s constraints.

• The get operation has an average time complexity of O(1) as well.

In the worst case, it will iterate through a linked list of length n at the mapped index, making it O(n).

However, this is also limited by

the constraints.

• The remove operation has a similar time complexity to the get operation, as it may need to traverse a linked list, making it O(1) on average but O(n) in the worst case.
• Space Complexity: The space complexity is O(N) due to the storage of N key-value pairs in the linked lists.

Reasoning Behind Our Approach

In this solution, we chose to implement a hashmap using an array of linked lists, which is a common approach for handling hash collisions.

This approach provides an efficient way to store and retrieve key-value pairs, even when multiple keys map to the same index.

By using the modulo operation to calculate the index for each key, we distribute the keys evenly across the array, reducing the likelihood of collisions.

This approach ensures that our solution is efficient and suitable for the problem’s constraints.

Related Interview Questions By Company:

• Arranging Coins LeetCode
• Missing Number LeetCode
• Find All Numbers Disappeared In An Array LeetCode

Related Interview Questions By Difficulty:

• First Missing Positive LeetCode
• Unique Email Addresses LeetCode
• Word Pattern LeetCode

Related Interview Questions By Category:

• Design Add And Search Words Data Structure LeetCode
• Swim In Rising Water LeetCode
• Path With Maximum Probability LeetCode

Conclusion

In this blog post, we’ve tackled the LeetCode problem Design Hashmap We’ve discussed the problem’s requirements, implemented the MyHashMap class, and analyzed the time and space complexity of our solution.

By using an array of linked lists and carefully handling hash collisions, we’ve created a functional and efficient hashmap.

This problem provides a great introduction to hash maps and their fundamental operations.

You can find the question link here.

If you found this blog post helpful, please like and engage for more coding and algorithm-related content.

If you have any questions, suggestions, or comments, feel free to share them below.

Happy coding!