Number of Unequal Triplets in Array

Difficulty: Easy | Acceptance: 73.30% | Paid: No Topics: Array, Hash Table, Sorting

You are given a 0-indexed array of positive integers nums. Find the number of triplets (i, j, k) such that i < j < k and nums[i] != nums[j], nums[i] != nums[k], and nums[j] != nums[k].

Return the number of triplets that meet the conditions.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Sorting and Grouping
• Approach 3: Hash Map (Optimal)

Examples

Example 1:

Input: nums = [4,4,2,4,3]
Output: 3
Explanation: The following triplets satisfy the conditions:
- (0, 2, 4) because 4 != 2 != 3
- (1, 2, 4) because 4 != 2 != 3
- (2, 3, 4) because 2 != 4 != 3

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: No triplets satisfy the conditions.

Constraints

3 <= nums.length <= 100
1 <= nums[i] <= 1000

Approach 1: Brute Force

Intuition Since the constraint on the array length is small (n <= 100), we can simply check every possible triplet of indices (i, j, k) to see if they satisfy the inequality conditions.

Steps

• Initialize a counter to 0.
• Use three nested loops to generate all combinations where 0 <= i < j < k < n.
• For each triplet, check if nums[i], nums[j], and nums[k] are all distinct.
• If they are, increment the counter.
• Return the counter.

class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] != nums[j] and nums[j] != nums[k] and nums[i] != nums[k]:
                        count += 1
        return count

Complexity

• Time: O(n³) — We iterate through all possible triplets.
• Space: O(1) — We only use a few variables for counting.
• Notes: Simple to implement but inefficient for large arrays. Acceptable here due to small constraints.

Approach 2: Sorting and Grouping

Intuition If we sort the array, identical numbers will be grouped together. We can then iterate through the array to identify the size of each group of identical numbers. Once we have the counts of each distinct number, we can calculate the number of triplets by choosing 3 distinct groups and multiplying their sizes.

Steps

• Sort the array in non-decreasing order.
• Iterate through the sorted array to count the frequency of each distinct number. Store these frequencies in a list.
• Use three nested loops to iterate through the frequency list. For every combination of three distinct frequencies (f1, f2, f3), add f1 * f2 * f3 to the result.
• Return the result.

class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        groups = []
        i = 0
        while i < n:
            j = i
            while j < n and nums[j] == nums[i]:
                j += 1
            groups.append(j - i)
            i = j
        
        m = len(groups)
        count = 0
        for i in range(m):
            for j in range(i + 1, m):
                for k in range(j + 1, m):
                    count += groups[i] * groups[j] * groups[k]
        return count

Complexity

• Time: O(n log n + m³) — Sorting takes O(n log n). The nested loops depend on m (number of distinct elements). In the worst case (all distinct), m = n, so O(n³). However, if values are limited, m is small.
• Space: O(n) or O(m) — To store the groups.
• Notes: Sorting simplifies the logic of finding distinct groups.

Approach 3: Hash Map (Optimal)

Intuition We can count the frequency of each number using a hash map. Then, we iterate through the unique numbers. For each number x, we can calculate how many valid triplets have x as the “middle” value (in terms of value, not index). The number of such triplets is: (count of numbers smaller than x) * (count of x) * (count of numbers larger than x). Summing this for all unique numbers gives the total answer.

Steps

• Count the frequency of each number in nums using a hash map.
• Get the unique keys (numbers) and sort them.
• Initialize left_count to 0 and total_count to the length of nums.
• Iterate through the sorted unique keys:
  • Let freq be the frequency of the current number.
  • Calculate right_count as total_count - left_count - freq.
  • Add left_count * freq * right_count to the result.
  • Update left_count by adding freq.
• Return the result.

from collections import Counter

class Solution:
    def unequalTriplets(self, nums: List[int]) -> int:
        counts = Counter(nums)
        keys = sorted(counts.keys())
        
        res = 0
        left = 0
        total = len(nums)
        
        for k in keys:
            freq = counts[k]
            right = total - left - freq
            res += left * freq * right
            left += freq
            
        return res

Complexity

• Time: O(n log n) — Counting is O(n), sorting keys is O(m log m). Since m <= n, it is O(n log n).
• Space: O(n) — To store the hash map.
• Notes: This is the most efficient approach for larger inputs, reducing the problem to a single pass over distinct values.