Skip to main content
Talentd

Minimum Distance Between Three Equal Elements I - Solution & Explanation

EasyArrayHash Table10 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array of integers and need the smallest distance between three indices i < j < k where nums[i] == nums[j] == nums[k]. The distance is typically measured as the span of the triple (k - i). If no value appears at least three times, the answer is -1.

Approach 1: Brute Force Triple Check (O(n^3) time, O(1) space)

Check every possible triple of indices using three nested loops. For each i, iterate j from i+1, then k from j+1. When nums[i] == nums[j] == nums[k], compute the distance k - i and track the minimum. This approach directly follows the definition of the problem but quickly becomes impractical because the number of combinations grows cubically. It works only for very small arrays and mainly helps verify correctness during early reasoning.

Approach 2: Hash Table with Last Occurrences (O(n) time, O(n) space)

Scan the array once and group indices by value using a hash table. For each number, maintain the last two indices where it appeared. When the same value appears again, you now have three occurrences. Compute the distance using the first stored index and the current index (k - i), update the minimum, and slide the window of stored indices forward. This works because any optimal triple must consist of three consecutive occurrences of the same value. Each element is processed once, and hash lookups are constant time.

The key idea is reducing the search space. Instead of checking all triples, you only evaluate triples formed by consecutive occurrences of the same number. This turns the problem into a simple linear scan over an array while using a hash table to remember positions.

Recommended for interviews: The hash table approach. Interviewers expect you to recognize that only consecutive occurrences of the same value matter. Mentioning the brute force solution shows you understand the problem definition, but optimizing it to O(n) with a hash map demonstrates strong problem-solving and data structure awareness.

Solution

We can use a hash table 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 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triple CheckO(n^3)O(1)Conceptual baseline or very small arrays
Hash Table with Last OccurrencesO(n)O(n)General case; optimal for unsorted arrays

Video Solution

Minimum Distance Between Three Equal Elements I and II | Dry Run | Leetcode 3741 and 3740 | MIK • codestorywithMIK • 6,481 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Distance Between Three Equal Elements I easy or hard?
The problem is classified as Easy. The main challenge is recognizing that only consecutive occurrences of the same value need to be considered, which allows a linear scan with a hash map instead of checking all possible triples.
Minimum Distance Between Three Equal Elements I Python/Java solution
Most implementations use a hash map that stores the last two indices for each value. As you iterate through the array, update the stored indices and compute the distance whenever a third occurrence is found. The same logic works in Python (dict), Java (HashMap), C++ (unordered_map), Go (map), and TypeScript (Map).
How to solve Minimum Distance Between Three Equal Elements I in O(n)?
Iterate through the array and maintain a hash map from value to its recent indices. For each new index, append it to that value's occurrence list. When the list reaches three elements, compute the distance between the first and third index, update the minimum answer, and drop the oldest index to keep only the latest two.
What is the best approach for Minimum Distance Between Three Equal Elements I?
The most efficient solution uses a hash table to track indices of each value while scanning the array once. Store the last two positions for every number. When a third occurrence appears, compute the distance between the first stored index and the current index. This approach runs in O(n) time with O(n) extra space.
Is Minimum Distance Between Three Equal Elements I asked at Google/Amazon/Meta?
Problems involving array frequency tracking and hash map indexing are common in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary in wording, the underlying pattern of tracking occurrences with a hash table appears frequently in coding interviews.
What data structure is used in Minimum Distance Between Three Equal Elements I?
A hash table (hash map) is the main data structure. It maps each number to the indices where it appears so you can quickly detect when the same value occurs three times and compute the distance between those indices.
What is the time complexity of Minimum Distance Between Three Equal Elements I?
The optimal solution runs in O(n) time because the array is processed once and each lookup in the hash table is constant time. Space complexity is O(n) in the worst case if all elements are distinct and must be stored in the map.

Ready to solve this problem?

Practice Minimum Distance Between Three Equal Elements I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays