Minimum Distance Between Three Equal Elements II

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, return -1.

Compared with Part I, the key difference is the constraint:

• n can now be as large as 10^5

So a brute-force approach is no longer practical.

The distance formula simplifies

Assume the chosen indices are ordered:

i < j < k

Then:

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

This is the whole trick.

The middle index j disappears from the formula. So the distance depends only on the leftmost and rightmost indices of the triple.

Why only consecutive occurrences matter

Suppose one value appears at positions:

p0 < p1 < p2 < p3 < ...

Any valid triple has distance:

2 * (rightmost - leftmost)

So for that value, the minimum answer must come from a triple with the smallest possible span. That means we only need to check:

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

In other words, only three consecutive occurrences can produce the minimum.

Successor-array idea

The editorial uses a nice trick:

1. Build a next array
2. Let next[i] mean: the next index after i where the same value appears
3. Then for every index i, the next two same-value positions are:
   • next[i]
   • next[next[i]]

If both exist, then these three indices form the consecutive triple starting at i.

Building next

We traverse from right to left.

For each value, we remember its most recent position seen so far.

When we are at index i:

• next[i] becomes the most recent occurrence of nums[i]
• then we update the most recent occurrence to i

Because nums[i] <= n, we can store that "most recent occurrence" array in plain O(n) space. This is the same core idea as the hash-table editorial, just a little simpler to code.

Algorithm

1. Initialize next with -1
2. Traverse from right to left and fill next
3. Traverse from left to right
4. For each i, let:
   • second = next[i]
   • third = next[second]
5. If both exist, update the answer with:

2 * (third - i)

class Solution {
    public int minimumDistance(int[] nums) {
        int n = nums.length;
        int[] next = new int[n];
        int[] last = new int[n + 1];

        for (int i = 0; i < n; i++) {
            next[i] = -1;
        }
        for (int value = 0; value <= n; value++) {
            last[value] = -1;
        }

        for (int i = n - 1; i >= 0; i--) {
            int value = nums[i];
            next[i] = last[value];
            last[value] = i;
        }

        int answer = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int second = next[i];
            if (second == -1) {
                continue;
            }

            int third = next[second];
            if (third == -1) {
                continue;
            }

            answer = Math.min(answer, (third - i) * 2);
        }

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

Dry run

Take:

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

The same-value links look like this:

• for 1: 0 -> 1 -> 5
• for 2: 2 -> 4 -> 6

Now scan each starting index:

• start at 0: second = 1, third = 5 distance = 2 * (5 - 0) = 10
• start at 2: second = 4, third = 6 distance = 2 * (6 - 2) = 8

Minimum answer = 8.

Why this is O(n)

We only do two linear passes:

• one reverse pass to build next
• one forward pass to test every consecutive triple

Every lookup is O(1), so the whole solution is linear.

Complexity analysis

Time Complexity: O(n)

Space Complexity: O(n)

Common mistakes

1. Forgetting that only consecutive occurrences matter

You do not need to test all triples of one value. If a triple skips an occurrence in the middle, its span is never better than a consecutive one.

2. Recomputing the full absolute-value expression

After sorting the indices, it always simplifies to 2 * (k - i).

3. Using a slow approach from Part I

Part I allows brute force because n <= 100. Here n <= 10^5, so we need linear or near-linear work.

Final takeaway

This problem looks like a three-index distance problem, but it is really a next occurrence problem.

Once we notice:

• the distance is just 2 * (rightmost - leftmost)
• the best triple must be consecutive

the solution becomes a clean next-array traversal.