Welcome to Subscribe On Youtube

3741. Minimum Distance Between Three Equal Elements II

Description

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 <= 105
  • 1 <= nums[i] <= n

Solutions

Solution 1: Hash Table

We can use a hash table $\textit{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 $\textit{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.

  • class Solution {
    public int minimumDistance(int[] nums) {
        int n = nums.length;
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            g.computeIfAbsent(nums[i], k -> new ArrayList<>()).add(i);
        }
        final int inf = 1 << 30;
        int ans = inf;
        for (var ls : g.values()) {
            int m = ls.size();
            for (int h = 0; h < m - 2; ++h) {
                int i = ls.get(h);
                int k = ls.get(h + 2);
                int t = (k - i) * 2;
                ans = Math.min(ans, t);
            }
        }
        return ans == inf ? -1 : ans;
    }
}


  • class Solution {
public:
    int minimumDistance(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> g;
        for (int i = 0; i < n; ++i) {
            g[nums[i]].push_back(i);
        }
        const int inf = 1 << 30;
        int ans = inf;
        for (auto& [_, ls] : g) {
            int m = ls.size();
            for (int h = 0; h < m - 2; ++h) {
                int i = ls[h];
                int k = ls[h + 2];
                int t = (k - i) * 2;
                ans = min(ans, t);
            }
        }
        return ans == inf ? -1 : ans;
    }
};


  • class Solution:
    def minimumDistance(self, nums: List[int]) -> int:
        g = defaultdict(list)
        for i, x in enumerate(nums):
            g[x].append(i)
        ans = inf
        for ls in g.values():
            for h in range(len(ls) - 2):
                i, k = ls[h], ls[h + 2]
                ans = min(ans, (k - i) * 2)
        return -1 if ans == inf else ans


  • func minimumDistance(nums []int) int {
	g := make(map[int][]int)
	for i, x := range nums {
		g[x] = append(g[x], i)
	}

	inf := 1 << 30
	ans := inf

	for _, ls := range g {
		m := len(ls)
		for h := 0; h < m-2; h++ {
			i := ls[h]
			k := ls[h+2]
			t := (k - i) * 2
			ans = min(ans, t)
		}
	}

	if ans == inf {
		return -1
	}
	return ans
}


  • function minimumDistance(nums: number[]): number {
    const n = nums.length;
    const g = new Map<number, number[]>();

    for (let i = 0; i < n; i++) {
        if (!g.has(nums[i])) {
            g.set(nums[i], []);
        }
        g.get(nums[i])!.push(i);
    }

    const inf = 1 << 30;
    let ans = inf;

    for (const ls of g.values()) {
        const m = ls.length;
        for (let h = 0; h < m - 2; h++) {
            const i = ls[h];
            const k = ls[h + 2];
            const t = (k - i) * 2;
            ans = Math.min(ans, t);
        }
    }

    return ans === inf ? -1 : ans;
}

All Problems

All Solutions