Difficulty: Easy | Acceptance: 73.50% | Paid: No Topics: Array, Hash Table
You are given a 0-indexed array nums consisting of positive integers.
Find three indices i, j, and k such that i < j < k and nums[i] = nums[j] = nums[k].
The distance of the triplet (i, j, k) is defined as k - i.
Return the minimum possible distance of a valid triplet (i, j, k), or return -1 if there is no such triplet.
- Examples
- Constraints
- Brute Force
- Hash Map
- Single Pass
Examples
Example 1:
Input: nums = [5,2,5,2,5,2]
Output: 4
Explanation: The minimum distance is achieved by the triplet (0, 2, 4) or (1, 3, 5).
Example 2:
Input: nums = [1,2,3,1,2,3]
Output: -1
Explanation: There is no triplet of equal elements.
Example 3:
Input: nums = [1,1,1,1]
Output: 2
Explanation: The minimum distance is achieved by the triplet (0, 1, 2) or (1, 2, 3).
Constraints
- 1 <= n == nums.length <= 100
- 1 <= nums[i] <= n
Brute Force
Intuition Check all possible triplets (i, j, k) where i < j < k and find the minimum distance where all three elements are equal.
Steps
- Iterate through all possible starting indices i
- For each i, iterate through all possible middle indices j > i
- If nums[i] == nums[j], iterate through all possible ending indices k > j
- If nums[j] == nums[k], update the minimum distance
- Return the minimum distance found, or -1 if no valid triplet exists
from typing import List
class Solution:
def minimumDistance(self, nums: List[int]) -> int:
n = len(nums)
min_dist = float('inf')
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
for k in range(j + 1, n):
if nums[j] == nums[k]:
min_dist = min(min_dist, k - i)
return min_dist if min_dist != float('inf') else -1
Complexity
- Time: O(n³) - Three nested loops
- Space: O(1) - Only using constant extra space
- Notes: Simple but inefficient for large inputs
Hash Map
Intuition Store all indices for each value in a hash map, then find the minimum distance between any three consecutive occurrences of the same value.
Steps
- Create a hash map to store lists of indices for each value
- Iterate through the array and populate the hash map
- For each value with at least 3 occurrences, check all consecutive triplets of indices
- Track the minimum distance across all values
- Return the minimum distance found, or -1 if no valid triplet exists
from typing import List
from collections import defaultdict
class Solution:
def minimumDistance(self, nums: List[int]) -> int:
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):
dist = idx_list[i + 2] - idx_list[i]
min_dist = min(min_dist, dist)
return min_dist if min_dist != float('inf') else -1
Complexity
- Time: O(n) - Single pass to build the map, then linear scan through all indices
- Space: O(n) - Hash map stores all indices
- Notes: Efficient and easy to understand
Single Pass
Intuition Maintain only the last two indices for each value. When we encounter a third occurrence, we can immediately calculate the distance and update the minimum.
Steps
- Create a hash map to store the last two indices for each value
- Iterate through the array
- For each element, if we already have two previous indices, calculate the distance
- Update the minimum distance and remove the oldest index
- Add the current index to the map
- Return the minimum distance found, or -1 if no valid triplet exists
from typing import List
from collections import defaultdict
class Solution:
def minimumDistance(self, nums: List[int]) -> int:
last_two = defaultdict(list)
min_dist = float('inf')
for i, num in enumerate(nums):
if num in last_two:
if len(last_two[num]) == 2:
dist = i - last_two[num][0]
min_dist = min(min_dist, dist)
last_two[num].pop(0)
last_two[num].append(i)
else:
last_two[num].append(i)
return min_dist if min_dist != float('inf') else -1
Complexity
- Time: O(n) - Single pass through the array
- Space: O(n) - Hash map stores at most 2 indices per unique value
- Notes: Most space-efficient approach while maintaining O(n) time complexity