Problem Statement in English

You’re given a 0-indexed integer array nums. A good tuple is defined as a tuple of three indices (i, j, k) such that:

  • i < j < k
  • nums[i] == nums[j] == nums[k]

Return the minimum distance of a good tuple. If no good tuple exists, return -1.

Approach

We can just isolate the indices of each unique element in the array and then find the minimum distance between any three indices for that element. We can use a hashmap to store the indices of each unique element.

The minimisation step is basically twice the distance between the first and the third index of the three indices we are considering.

Thus we can iterate through the list of indices for each unique element and calculate this distance for every three consecutive indices.

And we’re done!

Solution in Python


class Solution:
    def minimumDistance(self, nums: List[int]) -> int:
        hm = defaultdict(list)

        for i, n in enumerate(nums):
            hm[n].append(i)

        res = inf
        for k in hm.keys():
            l = hm[k]
            for i in range(2, len(l)):
                res = min(res, 2 * (l[i] - l[i - 2]))
        
        return res if res != inf else -1

Complexity

  • Time: $O(n)$
    Since we traverse the array once to build the hashmap and then traverse the hashmap to find the minimum distance.

  • Space: $O(n)$
    Since we store all indices of each unique element in the hashmap.

And we are done.