Finding the minimum distance between any pair of equal elements in an array
For some array of integers A = [a 0, a 1, ..., a n] find the minimum distance between i and j such that a i= a j and i! = j (or we will indicate that there are no such indices).
So, I implemented a naive O (n 2 ) method in C ++ that involves iterating through an array looking for equal elements and the corresponding minimum distance:
#include <vector>
#include <climits>
#include <algorithm>
int MinPair(const std::vector<int>& nums)
{
int ret = std::numeric_limits<int>::max();
for(int i = 0; i != nums.size(); ++i)
{
for(int j = 0; j != i; ++j)
{
if(nums[i] == nums[j])
ret = std::min(ret, i - j);
}
}
if(ret == std::numeric_limits<int>::max())
return -1;
return ret;
}
This works well, but I was told that there is a more "efficient" implementation that includes std :: map, without much clarification on which is more efficient. Namely, it was possible to go through the input array and store the first occurrence of an element in the map, and for each subsequent event, find the distance between this occurrence and the first index of this element on the map. If this distance is less than the current minimum, then we update this minimum.
However, I don't see how this is more "efficient". In terms of time complexity, you still have to go through the input array (O (n)) and use std :: map :: find to determine if an element is the first occurrence or not, is also O (n), which gives a complete complexity O (n 2 ). Cosmic complexity - you need to store the map in addition to the array / vector. What exactly am I missing here?
EDIT: I misjudged the map :: find was O (n); the input and search operations are actually O (log n), which can be seen right away, even assuming the main implementations use something like binary search.
source to share
I originally posted a coding solution that was similar to the solution grigor mentioned. Then I realized that there is an obvious optimization that makes everything work in O (N) time for best case and average case.
typedef pair<bool, int> LastPositionFound;
int MinPair(const std::vector<int>& nums)
{
unordered_map<int, LastPositionFound> table; // maps value found in array to the last position that value was seen at.
int best_distance = -1;
for (size_t index = 0; index < nums.size(); index++)
{
int value = nums[index];
LastPositionFound& lpf = table[value]; // returns {false,0} if not found
if (lpf.first)
{
int distance = index - lpf.second;
if ((distance < best_distance) || (best_distance == -1))
{
best_distance = distance;
}
}
// update reference to hash table entry
lpf.first = true;
lpf.second = index;
}
return best_distance;
}
source to share
You can map each item to its set of indices. Thus, you will have something like map<int, set<int>> m
and go through its vector: for(int i = 0, i < nums.size(); ++i) m[nums[i]].insert(i)
. After that, you can iterate over the map, and if the item has more than one index, find the minimum distance between the indices. Should be O (nlog (n)).
source to share