3741. Minimum Distance Between Three Equal Elements II

Array
Hash Table

TIME

O(n)

SPACE

O(n)

Intuition

Same as Part I. For indices i < j < k, the distance simplifies to:

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

The O(n) solution handles the larger constraints (n ≤ 10^5).

Solution

Group indices by their value using a hash map
For each value with at least 3 occurrences:
- Indices are naturally sorted (we process left to right)
- Check every 3 consecutive indices: span = indices[i+2] - indices[i]
Return minimum span × 2, or -1 if no valid tuple exists

Why Consecutive?

For sorted indices, the minimum span covering 3 elements is always achieved by 3 consecutive ones. Skipping an index only increases the span.

Complexity

Time: O(n), single pass to group, then process each group
Space: O(n), hash map storage

Edge Cases

Array length < 3 → return -1
No value appears 3+ times → return -1
All elements equal → use first 3 indices
Large arrays with many duplicates

Code

from typing import List
from collections import defaultdict


class Solution:
    def minimumDistance(self, nums: List[int]) -> int:
        """
        3741. Minimum Distance Between Three Equal Elements II
        Time: O(n)
        Space: O(n)
        """
        indices = defaultdict(list)

        for i, num in enumerate(nums):
            indices[num].append(i)

        min_dist = float('inf')

        for idx_list in indices.values():
            if len(idx_list) >= 3:
                for i in range(len(idx_list) - 2):
                    span = idx_list[i + 2] - idx_list[i]
                    min_dist = min(min_dist, 2 * span)

        return min_dist if min_dist != float('inf') else -1

import java.util.*;

/**
 * 3741. Minimum Distance Between Three Equal Elements II
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public int minimumDistance(int[] nums) {
        Map<Integer, List<Integer>> indices = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            indices.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }

        int minDist = Integer.MAX_VALUE;

        for (List<Integer> idxList : indices.values()) {
            if (idxList.size() >= 3) {
                for (int i = 0; i < idxList.size() - 2; i++) {
                    int span = idxList.get(i + 2) - idxList.get(i);
                    minDist = Math.min(minDist, 2 * span);
                }
            }
        }

        return minDist == Integer.MAX_VALUE ? -1 : minDist;
    }
}