Problem Statement

You are given an integer array nums.

A triple of indices (i, j, k) is called good if:

i, j, and k are distinct
nums[i] == nums[j] == nums[k]

The distance of a good triple is: $|i-j| + |j-k| + |k-i|$ ∣i−j∣+∣j−k∣+∣k−i∣

Your task is to return the minimum possible distance among all good triples. If no value appears at least 3 times, return -1.

Example

Input

nums = [1, 2, 1, 1, 3]

Good triple

The value 1 appears at indices 0, 2, 3.

So one good triple is (0, 2, 3).

Distance: $|0-2| + |2-3| + |3-0| = 2 + 1 + 3 = 6$ ∣0−2∣+∣2−3∣+∣3−0∣=2+1+3=6

Output

This matches the official example.

Step 1: Simplify the Formula

This is the most important observation in the problem.

Suppose the three indices are sorted: $a < b < c$ a<b<c

Then: $|a-b| + |b-c| + |c-a|$ ∣a−b∣+∣b−c∣+∣c−a∣

becomes: $(b-a) + (c-b) + (c-a)$ (b−a)+(c−b)+(c−a)

Now simplify: $(b-a) + (c-b) = c-a$ (b−a)+(c−b)=c−a

So total distance is: $(c-a) + (c-a) = 2(c-a)$ (c−a)+(c−a)=2(c−a)

That means the middle index does not affect the formula directly.

So for any valid triple: $\text{distance} = 2 \times (\text{largest index} – \text{smallest index})$ distance=2×(largest index−smallest index)

This is exactly the official hint.

Step 2: What Does This Mean?

If distance only depends on the smallest and largest index, then for any value that appears many times, we want three occurrences packed as closely together as possible.

Suppose a value appears at:

[1, 4, 7, 10]

Possible triples:

(1, 4, 7) → distance = 2 * (7 - 1) = 12
(4, 7, 10) → distance = 2 * (10 - 4) = 12
(1, 7, 10) → distance = 2 * (10 - 1) = 18

So the best triple comes from three consecutive occurrences, not from skipping one.

That leads to the core idea:

For each distinct value, collect all its indices.
Then check every window of 3 consecutive indices.

Step 3: Why Consecutive Triples Are Enough

Assume the positions of some value are:

p[0], p[1], p[2], ..., p[m-1]

If we choose any triple:

p[i], p[j], p[k]   where i < j < k

its distance is: $2 \times (p[k] – p[i])$ 2×(p[k]−p[i])

To minimize this, we want the gap p[k] - p[i] to be as small as possible.

For a fixed group of indices in sorted order, the smallest span for 3 chosen elements always comes from a contiguous block of length 3:

p[t], p[t+1], p[t+2]

So there is no need to try all combinations.

Step 4: Efficient Approach

Algorithm

Traverse the array.
Store all indices for each value in a hash map.
For each value:
- if it appears fewer than 3 times, skip it
- otherwise, check every consecutive triple of indices
- compute: $2 \times (indices[i+2] – indices[i])$ 2×(indices[i+2]−indices[i])
Return the minimum found, or -1 if none exists.

Step 5: Walkthrough

Consider:

nums = [5, 1, 5, 2, 5, 1, 5]

Indices by value:

5 -> [0, 2, 4, 6]
1 -> [1, 5]
2 -> [3]

For value 5, check consecutive triples:

(0, 2, 4) → distance = 2 * (4 - 0) = 8
(2, 4, 6) → distance = 2 * (6 - 2) = 8

Value 1 appears only twice, so ignore it.

Answer = 8

Step 6: Python Solution

from collections import defaultdict
from typing import List

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

        for i, x in enumerate(nums):
            positions[x].append(i)

        ans = float("inf")

        for idxs in positions.values():
            if len(idxs) < 3:
                continue

            for i in range(len(idxs) - 2):
                ans = min(ans, 2 * (idxs[i + 2] - idxs[i]))

        return -1 if ans == float("inf") else ans

Step 7: Complexity Analysis

Let n be the length of the array.

Building the index lists takes O(n)
Scanning all consecutive triples across all values also takes O(n) overall

So:

Time Complexity: O(n)
Space Complexity: O(n)

This fits the problem constraints where n can be up to 10^5.

Step 8: Why This Works

Key observation

For sorted indices a < b < c: $|a-b| + |b-c| + |c-a| = 2(c-a)$ ∣a−b∣+∣b−c∣+∣c−a∣=2(c−a)

So minimizing the distance is the same as minimizing the span from the first to the third chosen occurrence.

Key consequence

Among all ways to choose 3 occurrences of the same value, the minimum span must come from three consecutive positions in that value’s index list.

Therefore, checking all consecutive triples is enough.

Common Mistakes

1. Trying all triples

That would be too slow.
If one value appears many times, checking all combinations is expensive.

2. Not sorting indices

The indices are naturally collected in sorted order if you scan from left to right. That makes the window approach easy.

3. Missing the formula simplification

Without reducing the expression to 2 * (max - min), the problem looks harder than it is.

Final Takeaway

This problem looks like a triple-selection problem, but the math makes it much simpler.

The important insight is: $|i-j| + |j-k| + |k-i| = 2(\max(i,j,k) – \min(i,j,k))$ ∣i−j∣+∣j−k∣+∣k−i∣=2(max(i,j,k)−min(i,j,k))

So instead of thinking about all triples, think in terms of smallest span among 3 equal occurrences.

That turns the problem into:

group indices by value
slide a window of size 3
take the minimum span

Minimum Distance Between Three Equal Elements II Solution