Watch 9 video solutions for Minimum Distance Between Three Equal Elements II, a medium level problem involving Array, Hash Table. This walkthrough by Developer Coder has 246 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= nProblem 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.
| 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 |