Minimum Distance Between Three Equal Elements I

Problem summary

We need three distinct indices i, j, and k such that:

• nums[i] == nums[j] == nums[k]
• the total distance is as small as possible

If no value appears at least three times, the answer is -1.

Key observation

Assume the chosen indices are in sorted order: i < j < k.

Then:

abs(i - j) + abs(j - k) + abs(k - i) = (j - i) + (k - j) + (k - i) = 2 * (k - i)

That means the middle index does not affect the final formula directly. For any valid triple, the distance depends only on the leftmost and rightmost positions.

Even more important insight

Suppose some value appears at positions:

p0 < p1 < p2 < p3 < ...

If we choose any triple from these positions, its distance is:

2 * (rightmost - leftmost)

So to minimize the answer, we should minimize the span between the first and third chosen occurrence.

That means the best triple for one value is always formed by three consecutive occurrences:

• (p0, p1, p2)
• (p1, p2, p3)
• and so on

We never need to test non-consecutive triples.

One-pass approach

The constraints are small enough for brute force, but this observation gives a cleaner linear solution.

Since 1 <= nums[i] <= n, we can use arrays instead of a hash map.

For every value, track:

• its earliest index inside the current window of two recent occurrences
• its second recent index
• how many times it has appeared so far

When we see the:

• first occurrence, store it in first[value]
• second occurrence, store it in second[value]
• third or later occurrence at index i, we now have a consecutive triple

The distance of that triple is:

2 * (i - first[value])

After using it, slide the window forward:

• first[value] = second[value]
• second[value] = i

This checks every consecutive triple exactly once.

class Solution {
    public int minimumDistance(int[] nums) {
        int n = nums.length;
        int[] first = new int[n + 1];
        int[] second = new int[n + 1];
        int[] count = new int[n + 1];

        for (int value = 0; value <= n; value++) {
            first[value] = -1;
            second[value] = -1;
        }

        int answer = Integer.MAX_VALUE;

        for (int index = 0; index < n; index++) {
            int value = nums[index];
            count[value]++;

            if (count[value] == 1) {
                first[value] = index;
            } else if (count[value] == 2) {
                second[value] = index;
            } else {
                answer = Math.min(answer, (index - first[value]) * 2);
                first[value] = second[value];
                second[value] = index;
            }
        }

        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
}

Dry run

Take:

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

Occurrences:

• value 1 appears at 0, 1, 5
• value 2 appears at 2, 4, 6

For value 1, the triple span is 5 - 0 = 5, so distance = 10.

For value 2, the triple span is 6 - 2 = 4, so distance = 8.

The minimum answer is 8.

Why sliding the last two occurrences works

Imagine one value appears at:

p0 < p1 < p2 < p3

Then the useful triples are:

• (p0, p1, p2) with span p2 - p0
• (p1, p2, p3) with span p3 - p1

But triples like:

• (p0, p1, p3)
• (p0, p2, p3)

always have a larger span than at least one consecutive triple.

So once we finish checking the triple ending at p2, the next candidate only needs the last two positions and the new one.

Complexity analysis

Time Complexity: O(n)

• we scan the array once
• each index is processed in constant time

Space Complexity: O(n)

• we store occurrence state for values from 1 to n

Common mistakes

1. Computing the full absolute-value formula every time

Once the indices are ordered, the expression always becomes 2 * (k - i).

2. Checking all triples of the same value

That is unnecessary. Only consecutive triples can produce the minimum span.

3. Forgetting the -1 case

If no value appears at least three times, return -1.

Brute force is accepted too

Because n <= 100, a triple-loop solution also passes for Part I.

But this one-pass method is still nice to know because:

• the idea is cleaner once the formula simplifies
• it naturally matches the stronger Part II version
• it is easy to implement in every language