Design a HashMap without using any built-in hash table libraries. To be specific, your design should include these functions:

• put(key, value): Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
• get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• remove(key): Remove the mapping for the value key if this map contains the mapping for the key.

Examples:

Input: n = 8

• put(1, 1) 
• put(2, 2)
• get(1) 
• get(3)
• put(2, 1) 
• get(2)
• remove(2)
• get(2)

Output: 
1
-1
1
-1

Explanation: MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1); // returns 1
hashMap.get(3); // returns -1 (not found)
hashMap.put(2, 1); // update the existing value
hashMap.get(2); // returns 1 
hashMap.remove(2); // remove the mapping for 2
hashMap.get(2); // returns -1 (not found)

Input: n = 8

• put(1, 1) 
• put(2, 2)
• get(1) 
• get(2)
• put(3, 1) 
• get(3)
• remove(2)
• remove(3)

Output: 
1
2
1

Approach: To solve the problem follow the below idea:

We will use array size upto 1e6. We will initialize all the values of the array by -1, as a value to denote no element currently at this position. Thus, we can use this array for all of the functions mentioned above.

Steps that were to follow the above approach:

• There can be at max 10^4 key-value pairs so we create an array of size 10^4+ 1 (0-based indexing).
• We initialize all the array values with -1 because by default they are 0 in an empty array and our value for a particular key can also be 0. So if we don’t initialize with something else it will give us the wrong outputs.
• After that, everything is a piece of cake. We put() the given value at the specified index key and similarly get() the value stored at the index key.
• When removing, we just initialize the specified index key back to -1.

Below is the code to implement the above steps:

1
-1
1
-1

Time Complexity: O(1)
Auxiliary Space: O(1)