Watch 10 video solutions for Minimum Distance Between Three Equal Elements I, a easy level problem involving Array, Hash Table. This walkthrough by Developer Coder has 330 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 <= 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.
| 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 |