LeetCode 3741 - Minimum Distance Between Three Equal Elements II

LeetCode Problem 3741

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

Problem Understanding

The problem asks us to find three distinct indices (i, j, k) such that the values at those positions are identical:

nums[i] == nums[j] == nums[k]

Among all such valid triples, we must compute the minimum possible distance, where the distance is defined as:

abs(i - j) + abs(j - k) + abs(k - i)

If no value appears at least three times, then there is no valid tuple, and we must return -1.

The input is an integer array nums, where:

• nums[i] represents the value at index i
• indices in the tuple must be distinct
• array length can be as large as 10^5

The output is a single integer representing the minimum distance among all valid triples.

The most important observation comes from simplifying the distance formula. Suppose we sort the three indices:

a < b < c

Then:

abs(a - b) + abs(b - c) + abs(c - a)
= (b - a) + (c - b) + (c - a)
= 2(c - a)

This means the middle index does not directly matter. The distance depends only on the smallest and largest indices in the chosen triple.

This simplification dramatically changes how we think about the problem.

The constraints are important:

• n can be up to 100,000
• a cubic brute force solution would be far too slow
• we need something close to linear or O(n log n)

Several edge cases are important upfront. If every number appears fewer than three times, the answer is -1. If exactly three occurrences exist, that triple must be used. If a number appears many times, we need to identify the best consecutive group of three indices rather than checking every combination.

Approaches

Brute Force Approach

The most straightforward solution is to try every possible triple of indices (i, j, k).

For each triple:

1. Check whether all three values are equal.
2. Compute the distance.
3. Track the minimum distance.

This guarantees correctness because every possible valid tuple is examined.

However, this approach is far too slow. Since there are O(n³) triples, and n can be 100,000, the number of operations becomes astronomically large.

Even a slightly improved version, where we first group indices by value and test all combinations of three occurrences, is still too expensive. If one value appears m times, checking all triples costs:

O(m³)

which is still unacceptable in the worst case.

Key Insight for an Optimal Solution

The critical mathematical observation is:

For sorted indices:

a < b < c

the distance becomes:

2(c - a)

This means minimizing the distance is equivalent to minimizing:

c - a

For a fixed value, suppose its occurrences are:

[p1, p2, p3, p4, p5]

To minimize the range of three indices, we only need to check consecutive windows of size 3:

(p1, p2, p3)
(p2, p3, p4)
(p3, p4, p5)

Why?

Because any non-consecutive triple spans a larger interval than a consecutive one. If we want the smallest c - a, we should choose three occurrences that are as close together as possible.

We can therefore:

1. Group indices by value.
2. For each value with at least three occurrences:

• check every consecutive group of three indices
• compute distance as 2 * (rightmost - leftmost)

3. Return the minimum.

Since every index is processed once, the algorithm runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every possible triple
Optimal	O(n)	O(n)	Uses index grouping and sliding windows of size 3

Algorithm Walkthrough

Step 1: Group indices by value

Create a hash map where:

value -> list of indices

As we iterate through the array, append each index to the corresponding list.

For example:

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

becomes:

{
    1: [0,2,3],
    2: [1],
    3: [4]
}

We use a hash map because lookup and insertion are O(1) on average.

Step 2: Process only values with at least three occurrences

Any value appearing fewer than three times cannot form a valid tuple.

So we skip those immediately.

Step 3: Check consecutive triples

For each index list:

positions = [p1, p2, p3, p4, ...]

iterate over every window of size three:

(pi, pi+1, pi+2)

Compute:

distance = 2 × (positions[i+2] - positions[i])

Track the minimum.

Step 4: Return result

If we never found a valid triple, return:

-1

Otherwise, return the smallest distance found.

Why it works

The algorithm works because the distance formula simplifies to:

2(c - a)

after sorting the indices.

Therefore, minimizing the distance means minimizing the span between the smallest and largest index. Among a sorted occurrence list, the smallest span for any three elements must occur in a consecutive window of size three. Any non-consecutive choice skips closer indices and creates an equal or larger range.

Since we evaluate every consecutive triple for every value, the minimum valid distance is guaranteed to be found.

Python Solution

from collections import defaultdict
from typing import List

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

        for index, value in enumerate(nums):
            positions[value].append(index)

        min_distance = float("inf")

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

            for i in range(len(indices) - 2):
                distance = 2 * (indices[i + 2] - indices[i])
                min_distance = min(min_distance, distance)

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

The implementation begins by building a dictionary that maps each number to all positions where it appears. This allows us to quickly isolate indices belonging to the same value.

We then iterate through every list of positions. If the list contains fewer than three indices, we skip it because no valid tuple exists.

For lists with at least three occurrences, we examine every consecutive group of three indices. Since the distance formula simplifies to:

2 × (rightmost - leftmost)

we compute the result directly without needing absolute values.

Finally, if no valid triple was found, min_distance remains infinity and we return -1.

Go Solution

func minimumDistance(nums []int) int {
	positions := make(map[int][]int)

	for index, value := range nums {
		positions[value] = append(positions[value], index)
	}

	const inf = int(1e9)
	minDistance := inf

	for _, indices := range positions {
		if len(indices) < 3 {
			continue
		}

		for i := 0; i <= len(indices)-3; i++ {
			distance := 2 * (indices[i+2] - indices[i])

			if distance < minDistance {
				minDistance = distance
			}
		}
	}

	if minDistance == inf {
		return -1
	}

	return minDistance
}

The Go implementation follows the exact same algorithmic structure as the Python version.

Instead of defaultdict, we use a map[int][]int, where missing keys naturally start as nil slices and can safely be appended to.

Go integers are sufficient here because the maximum possible distance is bounded by:

2 × (n - 1)

and n ≤ 100000, so integer overflow is not a concern.

Worked Examples

Example 1

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

Step 1: Build positions map

Index	Value	Map State
0	1	{1:[0]}
1	2	{1:[0], 2:[1]}
2	1	{1:[0,2], 2:[1]}
3	1	{1:[0,2,3], 2:[1]}
4	3	{1:[0,2,3], 2:[1], 3:[4]}

Only value 1 appears at least three times.

Check consecutive triples:

Triple	Distance
(0,2,3)	2 × (3 - 0) = 6

Answer:

6

Example 2

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

Step 1: Build positions map

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

Check triples for value 1:

Triple	Distance
(0,1,5)	2 × (5 - 0) = 10

Check triples for value 2:

Triple	Distance
(2,4,6)	2 × (6 - 2) = 8

Minimum:

8

Example 3

nums = [1]

Positions:

1 -> [0]

No value appears three times.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is inserted once and processed at most once
Space	O(n)	Hash map stores all indices

The algorithm is linear because each array element contributes to exactly one stored index list, and every stored index participates in at most one sliding window iteration. Even though we process multiple groups, the total number of stored indices across all groups is exactly n.

Test Cases

sol = Solution()

assert sol.minimumDistance([1, 2, 1, 1, 3]) == 6  # Example 1
assert sol.minimumDistance([1, 1, 2, 3, 2, 1, 2]) == 8  # Example 2
assert sol.minimumDistance([1]) == -1  # Single element

assert sol.minimumDistance([1, 1]) == -1  # Fewer than three occurrences
assert sol.minimumDistance([5, 5, 5]) == 4  # Exactly three equal elements
assert sol.minimumDistance([7, 7, 7, 7]) == 4  # Multiple overlapping triples

assert sol.minimumDistance([1, 2, 1, 2, 1, 2]) == 8  # Multiple candidates
assert sol.minimumDistance([1, 1, 1, 1, 1]) == 4  # Dense repeated values

assert sol.minimumDistance([3, 1, 3, 2, 3, 1, 3]) == 4  # Best triple not first
assert sol.minimumDistance([1, 2, 3, 4, 5]) == -1  # No valid tuple

assert sol.minimumDistance([1] * 100000) == 4  # Stress test, large input

Test	Why
[1,2,1,1,3]	Validates Example 1
[1,1,2,3,2,1,2]	Validates Example 2
[1]	Smallest input
[1,1]	Fewer than three occurrences
[5,5,5]	Exactly one valid triple
[7,7,7,7]	Overlapping consecutive windows
[1,2,1,2,1,2]	Multiple repeated values
[1,1,1,1,1]	Dense duplicates
[3,1,3,2,3,1,3]	Best answer appears later
[1,2,3,4,5]	No valid tuple
[1] * 100000	Maximum constraint stress test

Edge Cases

One important edge case occurs when no number appears at least three times. A naive implementation might accidentally return an uninitialized minimum value or crash while computing triples. In this implementation, we only process lists of length at least three. If no valid tuple exists, the answer variable remains infinity, and we correctly return -1.

Another edge case happens when a number appears exactly three times. Since there is only one possible valid triple, the algorithm must evaluate it correctly without missing it. Because we iterate from index 0 through len(indices) - 3, the single window is processed naturally.

A subtle edge case appears when many occurrences exist and the best triple is not the first one. For example:

[3,1,3,2,3,1,3]

The value 3 occurs at:

[0,2,4,6]

The best triple is:

(0,2,4)

or

(2,4,6)

both producing distance 8.

A naive implementation that only checks the first or last triple would fail. Our sliding window over every consecutive group guarantees we evaluate all candidates.

Finally, consider the maximum input size where all values are identical:

[1,1,1,...,1]

with 100,000 elements. A brute force solution becomes impossible here, but our implementation remains efficient because it processes each index only once, resulting in linear time complexity.