LeetCode Problem 3740

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

LeetCode 3740 - Minimum Distance Between Three Equal Elements I

Problem Understanding

The problem gives us an integer array nums and asks us to find three distinct indices (i, j, k) such that all three positions contain the same value:

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

Such a triple is called a good tuple.

For every good tuple, we compute its distance:

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

Our goal is to find the minimum possible distance among all good tuples. If no value appears at least three times, then no good tuple exists and we must return -1.

The input consists of:

• An integer array nums
• Array length n where 1 <= n <= 100
• Values satisfy 1 <= nums[i] <= n

The output is a single integer:

• The smallest distance among all valid good tuples
• -1 if no good tuple exists

Because the array length is at most 100, the input size is very small. This means even relatively expensive algorithms may still be acceptable. However, we should still look for a cleaner and more efficient solution.

Several edge cases are important:

• Arrays with fewer than three occurrences of every value should return -1.
• Arrays where exactly one value appears three times should evaluate only that tuple.
• Arrays where a value appears more than three times require choosing the best three indices.
• Arrays of length 1 or 2 can never contain a good tuple.
• Multiple different values may each produce valid tuples, and we must return the smallest distance among all of them.

Approaches

Brute Force

The most direct approach is to examine every possible triple of indices.

For every combination (i, j, k) where i < j < k, we check whether:

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

If the triple is valid, we compute its distance and update the minimum answer.

This approach is guaranteed to find the correct answer because it explicitly evaluates every possible good tuple. However, it requires checking all index triples.

The number of triples is:

O(n³)

For each triple, the work is constant.

Although n ≤ 100 makes this technically feasible, we can do better by exploiting the structure of the distance formula.

Key Insight

Suppose the indices of a valid tuple are ordered:

a < b < c

Then:

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

Adding them together:

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

This is the crucial observation.

The middle index completely disappears from the formula.

Therefore, for any three equal elements at positions:

a < b < c

their distance is simply:

2 * (c - a)

To minimize the distance, we only need to minimize the span between the first and third chosen occurrence.

For a value appearing at positions:

p0 < p1 < p2 < ... < pm

the smallest span among any three occurrences is achieved by three consecutive occurrences:

pi, pi+1, pi+2

because any non-consecutive choice would produce a larger or equal outer gap.

Thus we can:

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

• Examine every consecutive block of three indices.
• Compute 2 * (positions[i+2] - positions[i]).

3. Return the minimum value found.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every possible triple
Optimal	O(n)	O(n)	Groups indices and examines consecutive triples

Algorithm Walkthrough

Optimal Algorithm

1. Create a hash map where each value maps to a list of its occurrence indices.
2. Traverse the array once.

For every index i, append i to the list corresponding to nums[i]. 3. Initialize the answer as infinity. 4. For every value's index list:

• If the list contains fewer than three indices, skip it because no good tuple can be formed.
• Otherwise, examine every consecutive group of three indices.

5. Suppose the consecutive indices are:

positions[i]
positions[i+1]
positions[i+2]

Let:

left = positions[i]
right = positions[i+2]

The distance equals:

2 * (right - left)

6. Update the minimum answer.
7. After processing all values:

• If the answer was never updated, return -1.
• Otherwise, return the minimum distance found.

Why it works

For any ordered triple of equal-value indices a < b < c, the distance simplifies to 2(c-a). Therefore, minimizing the distance is equivalent to minimizing the gap between the first and third selected occurrence. Among all triples chosen from a sorted occurrence list, the smallest such gap is always achieved by three consecutive occurrences. By checking every consecutive triple for every value, we evaluate all possible candidates that could produce the minimum distance, guaranteeing the correct answer.

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)

        answer = 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])
                answer = min(answer, distance)

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

The implementation begins by building a hash map from value to occurrence positions. Since we traverse the array from left to right, every position list is automatically sorted.

Next, we iterate through each value's occurrence list. Lists with fewer than three elements cannot form a good tuple and are skipped.

For every remaining list, we examine consecutive triples. Using the derived formula, the distance is simply twice the difference between the first and third positions.

The smallest distance encountered is tracked in answer. If no valid triple exists, answer remains infinity and we return -1.

Go Solution

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

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

	ans := int(^uint(0) >> 1) // Max int

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

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

	if ans == int(^uint(0)>>1) {
		return -1
	}

	return ans
}

The Go implementation follows exactly the same logic as the Python version. A map from integer value to a slice of occurrence indices is used instead of a Python dictionary. Since the maximum possible distance is small, standard integer arithmetic is completely safe and there are no overflow concerns. The sentinel value is initialized using the maximum representable int.

Worked Examples

Example 1

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

Build occurrence lists

Index	Value
0	1
1	2
2	1
3	1
4	3

Result:

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

Process value 1

Consecutive triple:

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

Minimum distance:

6

Answer:

6

Example 2

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

Build occurrence lists

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

Process value 1

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

Current answer:

10

Process value 2

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

Update answer:

min(10, 8) = 8

Final answer:

8

Example 3

nums = [1]

Occurrence list:

1 -> [0]

No value appears three times.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is stored once and each occurrence list is scanned once
Space	O(n)	Hash map stores all indices

The total number of stored indices across all lists is exactly n. When processing occurrence lists, every index participates in at most a constant amount of work. Therefore the overall running time is linear in the size of the array, and the auxiliary space is also linear.

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  # Example 3

assert sol.minimumDistance([1, 1]) == -1  # Fewer than three elements
assert sol.minimumDistance([5, 5, 5]) == 4  # Exactly one valid triple
assert sol.minimumDistance([1, 2, 3, 4]) == -1  # No repeated values

assert sol.minimumDistance([1, 1, 1, 1]) == 4  # Multiple triples, choose best
assert sol.minimumDistance([2, 2, 2, 2, 2]) == 4  # Many occurrences

assert sol.minimumDistance([1, 2, 1, 2, 1, 2]) == 8  # Two different values
assert sol.minimumDistance([3, 1, 3, 3, 1, 1]) == 6  # Minimum from either value

assert sol.minimumDistance([1, 2, 1, 3, 1, 4, 1]) == 8  # Non-adjacent occurrences
assert sol.minimumDistance([1, 1, 1, 2, 2, 2]) == 4  # Multiple valid groups

Test Summary

Test	Why
[1,2,1,1,3]	Official example
[1,1,2,3,2,1,2]	Official example with two candidate values
[1]	No valid tuple
[1,1]	Fewer than three elements
[5,5,5]	Smallest valid good tuple
[1,2,3,4]	No duplicates
[1,1,1,1]	Multiple overlapping triples
[2,2,2,2,2]	Many occurrences of same value
[1,2,1,2,1,2]	Multiple values appear three times
[3,1,3,3,1,1]	Different values compete for answer
[1,2,1,3,1,4,1]	Widely spaced occurrences
[1,1,1,2,2,2]	Multiple independent valid groups

Edge Cases

No Value Appears Three Times

A common mistake is assuming that every repeated value can form a good tuple. If every value appears at most twice, no valid triple exists and the correct answer is -1. The implementation handles this naturally because every occurrence list with fewer than three elements is skipped.

Exactly Three Occurrences

When a value appears exactly three times, there is only one possible good tuple. Some implementations unnecessarily search for alternative combinations. Our solution directly evaluates the single consecutive triple and computes its distance correctly.

More Than Three Occurrences

When a value appears many times, there can be numerous possible triples. A naive solution might try all combinations. The key observation that the distance depends only on the outermost indices allows us to consider only consecutive triples. This guarantees that the smallest possible span, and therefore the smallest possible distance, is found efficiently.

Multiple Values Produce Good Tuples

Different values may each have valid triples. The correct answer is the minimum distance among all of them. The implementation processes every value independently and maintains a global minimum, ensuring the best tuple overall is returned.