A linear solution taking advantage of sorted indexes

 This is an interesting problem: you'll be taking advantage that the indexes in an array by definition are already sorted. Hence, although you'll be using the fact that the indexes are sorted, you won't be sorting anything leading to a linear optimized solution. The idea is to keep a list of indexes for each value in the array. The list by definition will be sorted. Then do a linear scan of each list, calculating the distance and storing the overall min one. Code is down below, cheers, ACC.

Minimum Distance Between Three Equal Elements II - LeetCode

ou 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

public int MinimumDistance(int[] nums)
{
    Hashtable htSortedIndexes = new Hashtable();

    //O(n)
    for(int i=0;i());
        List sortedIndexes = (List)htSortedIndexes[nums[i]];
        sortedIndexes.Add(i);
    }

    //O(n)
    int minDistance = -1;
    foreach (int key in htSortedIndexes.Keys)
    {
        List sortedIndexes = (List)htSortedIndexes[key];
        for (int i = 0; i < sortedIndexes.Count - 2; i++)
        {
            int sum = 2 * (sortedIndexes[i + 2] - sortedIndexes[i]);
            minDistance = (minDistance == -1) ? sum : Math.Min(minDistance, sum);
        }
    }

    return minDistance;
}