CODEWITHSUNDEEP
c++arraysalgorithmvector
rw435
rw435

Reputation: 315

Finding the minimum distance between any pair of equal elements in an array

Given some array of integers A = [a0, a1, ..., an], find the minimum distance between ai and aj such that ai = aj and i != j (or indicate that no such indices exist).

So I've implemented a naive O(n2) approach in C++, involving iterating through the array looking for equal elements and updating the minimum distance appropriately:

#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 a more "efficient" implementation exists involving std::map, without much clarification on what is more efficient. Namely, one could walk through the input array and store the first occurrence of an element within a map, and for every subsequent occurrence find the distance between that occurrence and the first index of that element in the map. If that distance is less than the current minimum, then we update that minimum.

However, I fail to see in what way this is more "efficient." Time complexity-wise, you would still have to walk through the input array (O(n)), and using std::map::find to identify whether or not an element is the first occurrence or not is also O(n), giving a total complexity of O(n2). Space complexity-wise you have to store a map in addition to the array/vector. What exactly am I missing here?

EDIT: I incorrectly assumed map::find was O(n); insertion and find operations are in fact O(log n), which one can immediately see even assuming basic implementations using something like binary search.

Upvotes: 3

Views: 3264

Answers (2)

selbie
selbie

Reputation: 104589

I originally posted a coding solution that was similar to the solution mentioned by grigor. Then I realized there was an obvious optimization that makes the whole thing 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;
}

Upvotes: 3

grigor
grigor

Reputation: 1624

You could map each element to a set of its indices. So you'd have something like a map<int, set<int>> m, and go through your vector: for(int i = 0, i < nums.size(); ++i) m[nums[i]].insert(i). After that you can iterate through the map and if an element has more than one index find the minimum distance between indices. Should be O(nlog(n)).

Upvotes: 1

Related Questions