Minimum Distance Between Three Equal Elements II - Solution & Explanation
Problem Statement
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 <= 1051 <= nums[i] <= n
Approach Overview
Problem Overview: Given an integer array, find the minimum distance between three equal elements. Formally, choose indices i < j < k where nums[i] = nums[j] = nums[k] and minimize the distance k - i. If no value appears at least three times, return -1.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Check every possible triplet of indices (i, j, k) such that i < j < k. For each combination, compare the three values. If they match, compute the span k - i and track the minimum across all valid triplets. This approach directly models the problem but performs three nested iterations over the array. The time complexity becomes O(n^3), which quickly becomes impractical for large inputs. It is mainly useful as a baseline or for validating optimized solutions during development.
Approach 2: Hash Table Tracking Last Occurrences (O(n) time, O(n) space)
Use a hash table to track the recent indices where each value appears while scanning the array from left to right. For each number, maintain a small list (or queue) of its last few positions. When you encounter the same value again, append the current index to its list. Once the list contains at least three indices, compute the span between the current index and the third-most-recent occurrence: current_index - indices[-3]. Update the global minimum distance.
The key insight: the smallest valid window for three identical values always involves consecutive occurrences of that value. Older occurrences cannot produce a shorter span than the latest three. Because each index is processed once and hash lookups are constant time, the algorithm runs in O(n) time. Space complexity is O(n) in the worst case if all elements are unique, though each key stores only a few recent indices.
This method scales well and keeps the logic simple: iterate once, update a hash structure, and compute distances whenever a third occurrence appears.
Recommended for interviews: Start by describing the brute force triplet scan to demonstrate understanding of the requirement. Then move quickly to the hash table solution. Interviewers expect the O(n) approach because it leverages constant‑time lookups and incremental tracking of indices, a common pattern in array frequency and occurrence problems. Implementing the hash table approach clearly shows you recognize repeating-element patterns and know how to maintain minimal windows efficiently.
Solution
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.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplets | O(n^3) | O(1) | Conceptual baseline or very small arrays |
| Hash Table Tracking Indices | O(n) | O(n) | General case; optimal for large arrays and interview solutions |
Video Solution
Minimum Distance Between Three Equal Elements I and II | Dry Run | Leetcode 3741 and 3740 | MIK • codestorywithMIK • 6,481 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Distance Between Three Equal Elements II easy or hard?
Minimum Distance Between Three Equal Elements II Python/Java solution
How to solve Minimum Distance Between Three Equal Elements II in O(n)?
What is the best approach for Minimum Distance Between Three Equal Elements II?
Is Minimum Distance Between Three Equal Elements II asked at Google/Amazon/Meta?
What data structure is used in Minimum Distance Between Three Equal Elements II?
What is the time complexity of Minimum Distance Between Three Equal Elements II?
Ready to solve this problem?
Practice Minimum Distance Between Three Equal Elements II with our built-in code editor and test cases.
Practice on FleetCode