3740. Minimum Distance Between Three Equal Elements I

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

 

Solutions

Solution: Hash Table

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const minimumDistance = function (nums) {
  const n = nums.length;
  const numMap = new Map();
  let result = Number.MAX_SAFE_INTEGER;

  for (let index = 0; index < n; index++) {
    const num = nums[index];

    if (!numMap.has(num)) {
      numMap.set(num, []);
    }

    numMap.get(num).push(index);
  }

  for (const indices of numMap.values()) {
    const len = indices.length;

    if (len < 3) continue;

    for (let index = 2; index < len; index++) {
      const i = indices[index];
      const j = indices[index - 1];
      const k = indices[index - 2];
      const dis = i - j + i - k + j - k;

      result = Math.min(dis, result);
    }
  }

  return result === Number.MAX_SAFE_INTEGER ? -1 : result;
};