Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For sorted indices a < b < c, the sum of their three pairwise distances is 2 * (c - a). Only the outer span matters. Among occurrences of one value, a minimum-span triple can always use three consecutive occurrences; skipping an occurrence cannot make the span smaller.

Approach

Group each value's indices into a list while scanning the array. These lists are already sorted. For every list containing at least three positions, inspect each consecutive triple, compute its pairwise-distance sum, and retain the minimum across all values.

If no list contains a triple, return -1. Otherwise return the smallest recorded distance. Any nonconsecutive triple contains a consecutive triple of the same value inside its outer interval, with no larger span, so considering only consecutive triples loses no optimum. The total length of all occurrence lists is the array length.

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

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

        res = inf

        for arr in mp.values():
            for i in range(len(arr) - 2):
                a, b, c = arr[i], arr[i + 1], arr[i + 2]
                res = min(res, abs(a - b) + abs(b - c) + abs(a - c))

        return res if res != inf else -1

Complexity analysis

Let n = nums.length. Time: O(n). Auxiliary space: O(n) for value-to-index lists.