Problem #1 Find Closest Pairs [Part 1] | AlgoTips

Problem #1 Find Closest Pairs [Part 1]
Please leave your solutions in the comments with big-O complexity of running time and space!
Stay tuned.

[LackedMule]

Here’s my attempt at a solution:

You create a hash table with the number of rows equal to len(set(A)). Its keys are composed of the <distinct numbers in A> while its values are each the <latest index of key in A>. All the while, you also have a variable (call it minDistance) that keeps track of the smallest distance of all key pairs.

Here’s my pseudocode:

init hashTable;
minDistance = inf;

for (int i = 0; i < len(A); i++)
if A[i] in hashTable:
int dis = i - hashTable[A[i]];
hashTable[A[i]] = i; // update index of key
minDistance = (dis < minDistance) ? dis : minDistance;
else:
hashTable.insert(A[i], i);

return (minDistance == inf) ? -1 : minDistance

This solution has a complexity of O(n) in both space and time.

[algotips]

Problem #1 Find Closest Pairs [Part 1]
Please leave your solutions in the comments with big-O complexity of running time and space!
Stay tuned until the end for a HINT!