#706

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Design HashMap

Implement a custom HashMap from scratch using array scanning and hash lookup without built-in libraries for efficient key-value management.

array hash table linked list design hash function

Problem Statement

Design a HashMap that stores integer key-value pairs without using any built-in hash table libraries. Implement the MyHashMap class with methods to add, retrieve, and remove keys efficiently using an underlying array and hash lookup.

Your implementation should support three operations: put(key, value) to insert or update a key, get(key) to retrieve the value (or -1 if not found), and remove(key) to delete a key. Ensure correct handling of collisions and updates while maintaining performance constraints of up to 10^4 calls and keys in the range 0 to 10^6.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); // The map is now [[1,1]] myHashMap.put(2, 2); // The map is now [[1,1], [2,2]] myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]] myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]] myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value) myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]] myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]] myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]

Constraints

0 <= key, value <= 106
At most 104 calls will be made to put, get, and remove.

Solution Approach

Simple Array Scanning

Use a list of key-value pairs and scan linearly for each operation. This guarantees correctness but results in O(n) time for get, put, and remove, which may be acceptable for small input sizes.

Bucketed Hashing

Implement an array of buckets, each as a linked list, and use a hash function to determine the bucket for each key. This reduces average operation time to O(1) per bucket access, handling collisions gracefully with linked lists.

Optimized Array with Direct Indexing

If key ranges are small, use a fixed-size array indexed directly by key. Each entry stores the value or a sentinel for missing keys. This yields true O(1) time per operation but increases space usage proportional to the maximum key.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity varies: naive array scanning is O(n) per operation, bucketed hashing averages O(1) per operation, and direct-indexing array is O(1). Space complexity ranges from O(n) for linked-list buckets to O(maxKey) for direct-index arrays.

What Interviewers Usually Probe

Candidate discusses handling collisions explicitly with linked lists or arrays.
Candidate suggests hash function or modulus operation to distribute keys across buckets.
Candidate considers update behavior and removal edge cases carefully.

Common Pitfalls or Variants

Common pitfalls

Forgetting to update an existing key rather than adding a duplicate entry.
Not handling removal correctly, leaving stale entries in buckets.
Using inefficient scanning without buckets, causing timeouts on larger input sizes.

Follow-up variants

Design HashMap with chaining using balanced BSTs instead of linked lists for buckets.
Implement HashMap with open addressing and linear probing to resolve collisions.
Create a generic HashMap supporting string keys using the same array scanning plus hash lookup pattern.

FAQ

What is the main idea behind Design HashMap?

The problem focuses on implementing a HashMap from scratch using array scanning and hash lookup without built-in libraries.

How do you handle collisions in Design HashMap?

Use buckets with linked lists to store multiple key-value pairs or apply open addressing techniques to resolve collisions.

What are the time complexities for each operation?

Array scanning yields O(n), bucketed hashing averages O(1), and direct-indexing array provides O(1) per put, get, or remove.

Can keys be updated in this HashMap implementation?

Yes, if a key already exists, the put operation must update its value rather than adding a duplicate.

Is there a space trade-off in Design HashMap?

Yes, using direct-indexing arrays uses O(maxKey) space, while linked-list buckets are more space-efficient at O(n).

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class MyHashMap:
    def __init__(self):
        self.data = [-1] * 1000001

    def put(self, key: int, value: int) -> None:
        self.data[key] = value

    def get(self, key: int) -> int:
        return self.data[key]

    def remove(self, key: int) -> None:
        self.data[key] = -1


# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

Continue Practicing

#705 design hashset #745 prefix and suffix search #641 design circular deque