You are given an integer array nums.
A tuple (i, j, k) of 3 distinct indices is good if nums[i] == nums[j] == nums[k].
The distance of a good tuple is abs(i - j) + abs(j - k) + abs(k - i), where abs(x) denotes the absolute value of x.
Return an integer denoting the minimum possible distance of a good tuple. If no good tuples exist, return -1.
Example 1:
Input: nums = [1,2,1,1,3]
Output: 6
Explanation:
The minimum distance is achieved by the good tuple (0, 2, 3).
(0, 2, 3) is a good tuple because nums[0] == nums[2] == nums[3] == 1. Its distance is abs(0 - 2) + abs(2 - 3) + abs(3 - 0) = 2 + 1 + 3 = 6.
Example 2:
Input: nums = [1,1,2,3,2,1,2]
Output: 8
Explanation:
The minimum distance is achieved by the good tuple (2, 4, 6).
(2, 4, 6) is a good tuple because nums[2] == nums[4] == nums[6] == 2. Its distance is abs(2 - 4) + abs(4 - 6) + abs(6 - 2) = 2 + 2 + 4 = 8.
Example 3:
Input: nums = [1]
Output: -1
Explanation:
There are no good tuples. Therefore, the answer is -1.
Constraints:
1 <= n == nums.length <= 1001 <= nums[i] <= nProblem Overview: You are given an array of integers and need the smallest distance between three indices i < j < k where nums[i] == nums[j] == nums[k]. The distance is typically measured as the span of the triple (k - i). If no value appears at least three times, the answer is -1.
Approach 1: Brute Force Triple Check (O(n^3) time, O(1) space)
Check every possible triple of indices using three nested loops. For each i, iterate j from i+1, then k from j+1. When nums[i] == nums[j] == nums[k], compute the distance k - i and track the minimum. This approach directly follows the definition of the problem but quickly becomes impractical because the number of combinations grows cubically. It works only for very small arrays and mainly helps verify correctness during early reasoning.
Approach 2: Hash Table with Last Occurrences (O(n) time, O(n) space)
Scan the array once and group indices by value using a hash table. For each number, maintain the last two indices where it appeared. When the same value appears again, you now have three occurrences. Compute the distance using the first stored index and the current index (k - i), update the minimum, and slide the window of stored indices forward. This works because any optimal triple must consist of three consecutive occurrences of the same value. Each element is processed once, and hash lookups are constant time.
The key idea is reducing the search space. Instead of checking all triples, you only evaluate triples formed by consecutive occurrences of the same number. This turns the problem into a simple linear scan over an array while using a hash table to remember positions.
Recommended for interviews: The hash table approach. Interviewers expect you to recognize that only consecutive occurrences of the same value matter. Mentioning the brute force solution shows you understand the problem definition, but optimizing it to O(n) with a hash map demonstrates strong problem-solving and data structure awareness.
We can use a hash table g to store the list of indices for each number in the array. While traversing the array, we add each number's index to its corresponding list in the hash table. Define a variable ans to store the answer, with an initial value of infinity infty.
Next, we iterate through each index list in the hash table. If the length of an index list for a particular number is greater than or equal to 3, it means there exists a valid triplet. To minimize the distance, we can choose three consecutive indices i, j, and k from that number's index list, where i < j < k. The distance of this triplet is j - i + k - j + k - i = 2 times (k - i). We traverse all combinations of three consecutive indices in the list, calculate the distance, and update the answer.
Finally, if the answer is still the initial value infty, it means no valid triplet exists, so we return -1; otherwise, we return the calculated minimum distance.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triple Check | O(n^3) | O(1) | Conceptual baseline or very small arrays |
| Hash Table with Last Occurrences | O(n) | O(n) | General case; optimal for unsorted arrays |
Minimum Distance Between Three Equal Elements I | Weekly Contest 475 | Java| Developer Coder • Developer Coder • 330 views views
Watch 9 more video solutions →Practice Minimum Distance Between Three Equal Elements I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor