3741. Minimum Distance Between Three Equal Elements II

MediumArrayHash Table

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

A tuple (i, j, k) consisting of 3 distinct indices is considered good if all three elements at those positions are equal, that is, nums[i] == nums[j] == nums[k].

For any good tuple, its distance is defined as abs(i - j) + abs(j - k) + abs(k - i), where abs(x) represents the absolute value of x.

Your task is to find and return the minimum possible distance among all good tuples in the array. If there are no good tuples (meaning no value appears at least three times), return -1.

Key observations:

A good tuple requires three different indices i, j, and k whose corresponding values in nums are all the same.
The distance formula abs(i - j) + abs(j - k) + abs(k - i) measures how spread out these three indices are. If we order the indices so that i < j < k, this simplifies to (j - i) + (k - j) + (k - i) = 2 * (k - i), which depends only on the gap between the smallest and largest of the three indices.
To make the distance as small as possible, the three chosen indices should be as close together as possible. This means picking three consecutive positions (in sorted order) where the same value appears.

If a particular value occurs fewer than three times, it cannot form a good tuple. When no value in the array occurs at least three times, the answer is -1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

Grouping indices by value and sliding a window of three consecutive occurrences finds the minimum gap with hash-table-based index storage.

Open in Flowchart

Intuition

The first thing to notice is the structure of the distance formula. For three indices i, j, and k, the distance is abs(i - j) + abs(j - k) + abs(k - i). The absolute values look complicated at first, but if we sort the three indices so that i < j < k, the formula simplifies nicely:

(j - i) + (k - j) + (k - i) = 2 * (k - i)

This is a key insight: the distance depends only on the gap between the smallest and largest index. The middle index j cancels out completely and does not affect the result. So to minimize the distance, we just need to make the gap between the smallest and largest chosen index as small as possible.

The second thing to notice is the constraint that all three values must be equal. This means we only care about groups of indices that share the same value. A natural way to organize this is to collect, for each distinct value, the list of positions where it appears. Since we scan the array from left to right, the positions in each list are automatically stored in increasing order.

Now, within a single value's sorted list of indices, we want three positions where the gap between the outermost two (k - i) is minimized. The crucial realization is that we should always pick three consecutive positions from this sorted list. Why? Because if we skip a position in the middle, we are forced to spread the outer two indices further apart, which only increases k - i. By keeping the three indices consecutive in the list, the gap k - i stays as tight as possible.

So for each value's index list ls, we slide a window of three consecutive entries and compute 2 * (ls[h + 2] - ls[h]), keeping track of the smallest result. A value that appears fewer than three times simply has no window of size three, so it contributes nothing.

Finally, if we never find any value appearing at least three times, no good tuple exists, and the answer remains its initial value of infinity, in which case we return -1.

Solution Approach

Solution 1: Hash Table

We use a hash table g to store the list of indices for each number in the array. While traversing nums, we add each number's index to its corresponding list in the hash table. Because we scan from left to right, every list ends up sorted in increasing order of indices automatically.

We define a variable ans to hold the answer, initialized to infinity inf.

Next, we iterate through each index list ls in the hash table. If a list has length greater than or equal to 3, it means a valid triplet exists for that number. To minimize the distance, we choose three consecutive indices i, j, and k from the list, where i < j < k. As shown earlier, the distance of such a triplet simplifies to j - i + k - j + k - i = 2 * (k - i), which only depends on the outer two indices.

So for each list, we slide a window of three consecutive entries: for each starting position h, we take i = ls[h] and k = ls[h + 2], compute (k - i) * 2, and update ans with the smaller value. Lists with fewer than three indices produce no valid window and are naturally skipped, since the loop range(len(ls) - 2) runs zero times.

Finally, if ans is still its initial value inf, no valid triplet exists, so we return -1; otherwise, we return the computed minimum distance.

The time complexity is O(n), where n is the length of the array, since we process each index a constant number of times. The space complexity is O(n) for storing all indices in the hash table.

Example Walkthrough

Let's trace through the solution with a small example: nums = [2, 5, 2, 8, 2, 5, 5, 5].

Step 1: Build the hash table of indices.

We scan nums from left to right, appending each element's index to its value's list:

Index	Value	Action
0	2	`g[2] = [0]`
1	5	`g[5] = [1]`
2	2	`g[2] = [0, 2]`
3	8	`g[8] = [3]`
4	2	`g[2] = [0, 2, 4]`
5	5	`g[5] = [1, 5]`
6	5	`g[5] = [1, 5, 6]`
7	5	`g[5] = [1, 5, 6, 7]`

After scanning, the hash table is:

g = {
  2: [0, 2, 4],
  5: [1, 5, 6, 7],
  8: [3]
}

Notice each list is already sorted in increasing order, since we scanned left to right.

Step 2: Initialize the answer.

We set ans = inf.

Step 3: Process each value's index list with a sliding window of size 3.

Value 8 → [3]: Length is 1, which is less than 3. The loop range(1 - 2) runs zero times, so it's skipped. No good tuple here.
Value 2 → [0, 2, 4]: Length is 3, so exactly one window exists.
- Window at h = 0: i = ls[0] = 0, k = ls[2] = 4. Distance = (4 - 0) * 2 = 8.
- Update ans = min(inf, 8) = 8.
Value 5 → [1, 5, 6, 7]: Length is 4, so two windows exist.
- Window at h = 0: i = ls[0] = 1, k = ls[2] = 6. Distance = (6 - 1) * 2 = 10.
  - Update ans = min(8, 10) = 8.
- Window at h = 1: i = ls[1] = 5, k = ls[3] = 7. Distance = (7 - 5) * 2 = 4.
  - Update ans = min(8, 4) = 4.

Step 4: Return the result.

After processing all lists, ans = 4, which is no longer inf, so we return 4.

Verifying the winning tuple: The minimum came from value 5 at the consecutive positions (5, 6, 7). Let's confirm with the original formula using i = 5, j = 6, k = 7:

abs(5 - 6) + abs(6 - 7) + abs(7 - 5) = 1 + 1 + 2 = 4 ✓

This matches our simplified computation 2 * (k - i) = 2 * (7 - 5) = 4.

Key takeaways from this trace:

Choosing three consecutive positions within a value's list mattered: for value 5, the tight window (5, 6, 7) gave 4, far better than the wider window (1, 6) which gave 10.
The middle index plays no role in the distance—only the gap between the outer two indices counts.
Values appearing fewer than three times (like 8) are naturally skipped by the empty range, requiring no special handling.

Solution Implementation

1from typing import List
2from collections import defaultdict
3from math import inf
4
5
6class Solution:
7    def minimumDistance(self, nums: List[int]) -> int:
8        # Group the indices by their value.
9        # value_to_indices[value] = list of indices where this value appears (in ascending order).
10        value_to_indices = defaultdict(list)
11        for index, value in enumerate(nums):
12            value_to_indices[value].append(index)
13
14        # Track the minimum distance found across all groups.
15        min_distance = inf
16
17        # For each value group, examine every window of three equal values.
18        for indices in value_to_indices.values():
19            # Slide a window of size 3 over the sorted indices.
20            for start in range(len(indices) - 2):
21                left_index = indices[start]        # First index in the window.
22                right_index = indices[start + 2]   # Third index in the window.
23
24                # The span between the outer two indices, doubled per the problem's metric.
25                min_distance = min(min_distance, (right_index - left_index) * 2)
26
27        # Return -1 if no valid triple exists; otherwise return the minimum distance.
28        return -1 if min_distance == inf else min_distance
29

1class Solution {
2    public int minimumDistance(int[] nums) {
3        int n = nums.length;
4
5        // Group the indices of elements that share the same value.
6        // key   -> the value found in nums
7        // value -> the list of indices (in ascending order) holding that value
8        Map<Integer, List<Integer>> valueToIndices = new HashMap<>();
9        for (int i = 0; i < n; i++) {
10            valueToIndices.computeIfAbsent(nums[i], key -> new ArrayList<>()).add(i);
11        }
12
13        final int INF = 1 << 30;
14        int answer = INF;
15
16        // For every group of equal values, examine indices that are two apart
17        // within the group (i.e. index h and index h + 2).
18        for (List<Integer> indices : valueToIndices.values()) {
19            int size = indices.size();
20            for (int h = 0; h < size - 2; h++) {
21                int left = indices.get(h);          // earlier index in the group
22                int right = indices.get(h + 2);     // index two positions later
23                int distance = (right - left) * 2;  // candidate distance (doubled)
24                answer = Math.min(answer, distance);
25            }
26        }
27
28        // If no valid pair was found, return -1; otherwise return the minimum distance.
29        return answer == INF ? -1 : answer;
30    }
31}
32

1class Solution {
2public:
3    int minimumDistance(vector<int>& nums) {
4        int n = nums.size();
5
6        // Group indices by their value.
7        // Key   -> a value present in nums
8        // Value -> the list of indices where that value appears (in ascending order)
9        unordered_map<int, vector<int>> valueToIndices;
10        for (int i = 0; i < n; ++i) {
11            valueToIndices[nums[i]].push_back(i);
12        }
13
14        const int kInf = 1 << 30;
15        int answer = kInf;
16
17        // For each value, look at indices that are two positions apart in the list.
18        // Because the indices are sorted, (right - left) gives the index span,
19        // and multiplying by 2 yields the distance metric we are minimizing.
20        for (auto& [value, indices] : valueToIndices) {
21            int size = indices.size();
22            for (int h = 0; h + 2 < size; ++h) {
23                int leftIndex = indices[h];
24                int rightIndex = indices[h + 2];
25                int distance = (rightIndex - leftIndex) * 2;
26                answer = min(answer, distance);
27            }
28        }
29
30        // If no valid triple was found, return -1.
31        return answer == kInf ? -1 : answer;
32    }
33};
34

1/**
2 * Finds the minimum distance metric based on grouping indices by equal values.
3 *
4 * For every value that appears in `nums`, the positions where it occurs are collected.
5 * Within each group of equal values, pairs of indices that are two apart in the
6 * group (positions `h` and `h + 2`) are examined, and `(k - i) * 2` is used as a
7 * candidate result. The smallest such candidate across all groups is returned.
8 *
9 * @param nums - The input array of numbers.
10 * @returns The minimum computed distance, or -1 if no valid pair exists.
11 */
12function minimumDistance(nums: number[]): number {
13    const length = nums.length;
14
15    // Map each value to the list of indices where it appears.
16    const valueToIndices = new Map<number, number[]>();
17
18    for (let i = 0; i < length; i++) {
19        const value = nums[i];
20        if (!valueToIndices.has(value)) {
21            valueToIndices.set(value, []);
22        }
23        valueToIndices.get(value)!.push(i);
24    }
25
26    // Use a large sentinel value to represent "infinity".
27    const infinity = 1 << 30;
28    let answer = infinity;
29
30    // Examine each group of indices that share the same value.
31    for (const indices of valueToIndices.values()) {
32        const groupSize = indices.length;
33
34        // Compare each index with the one two positions later in the group.
35        for (let h = 0; h < groupSize - 2; h++) {
36            const left = indices[h];
37            const right = indices[h + 2];
38            const candidate = (right - left) * 2;
39            answer = Math.min(answer, candidate);
40        }
41    }
42
43    // If no valid candidate was found, return -1.
44    return answer === infinity ? -1 : answer;
45}
46

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The first loop iterates over all elements of nums to build the dictionary g, which takes O(n) time.
The nested loops then iterate over each group ls in g.values(). For each group, the inner loop runs at most len(ls) - 2 times. Since the sum of the lengths of all groups equals n (each index appears in exactly one group), the total number of iterations across all groups is bounded by O(n).
Therefore, the overall time complexity is O(n).

Space Complexity: O(n), where n is the length of the array nums.

The dictionary g stores all indices of the elements in nums. In total, it holds n indices distributed across its keys, so the space used is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to multiply the span by 2

The most frequent mistake is returning right_index - left_index instead of (right_index - left_index) * 2. People correctly identify that the minimum distance comes from three consecutive indices in sorted order, but they forget that the distance formula abs(i - j) + abs(j - k) + abs(k - i) simplifies to 2 * (k - i), not just (k - i).

Why it happens: When you sort the indices so that i < j < k, the formula becomes (j - i) + (k - j) + (k - i). The first two terms telescope to (k - i), and adding the third (k - i) gives 2 * (k - i). It's easy to stop at the telescoping step and forget the final term.

Solution: Always derive the simplified formula carefully and double the span:

min_distance = min(min_distance, (right_index - left_index) * 2)

Pitfall 2: Assuming the middle index `j` matters

A subtle misconception is believing you must search over the middle index j as well, leading to an unnecessary O(n^3) or O(n^2) brute-force approach. Since the simplified distance 2 * (k - i) depends only on the outer indices, the choice of j is irrelevant to the distance value—it just needs to exist strictly between i and k.

Why it happens: The original three-term formula visually suggests all three indices contribute independently, masking the fact that the middle term cancels out.

Solution: Recognize that for any window of three consecutive equal-valued indices, the inner index is automatically valid. Only slide a window of size 3 and compare the outer pair:

for start in range(len(indices) - 2):
    left_index = indices[start]
    right_index = indices[start + 2]
    min_distance = min(min_distance, (right_index - left_index) * 2)

Pitfall 3: Not using consecutive indices within a group

Some attempts pick the global first, middle, and last occurrence of a value, or try arbitrary combinations, instead of choosing three consecutive occurrences. Because indices in each group are already sorted, the minimum (k - i) always comes from adjacent entries spaced two apart (indices[start] and indices[start + 2]).

Why it happens: It's tempting to think the closest triple involves the first and last occurrences, but that maximizes the span rather than minimizing it.

Solution: Slide a fixed window of size 3 across each sorted group and never skip entries, guaranteeing you evaluate the tightest possible clusters.

Pitfall 4: Mishandling the "no valid triple" case

Returning 0 or crashing when no value appears three or more times is a common error. If min_distance is never updated, it remains inf, which must be translated to -1.

Why it happens: Developers may initialize min_distance to 0 or another sentinel, or forget the final check entirely. The loop range(len(indices) - 2) silently runs zero times for short groups, so no error surfaces—just an incorrect inf result.

Solution: Initialize to inf and explicitly convert it back at the end:

return -1 if min_distance == inf else min_distance

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering