Problem

You are given a 0-indexed array of positive integers nums. Find the number of triplets (i, j, k) that meet the following conditions:

  • 0 <= i < j < k < nums.length
  • nums[i], nums[j], and nums[k] are pairwise distinct.
  • In other words, nums[i] != nums[j], nums[i] != nums[k], and nums[j] != nums[k].

Return the number of triplets that meet the conditions.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: nums = [4,4,2,4,3]
Output: 3
Explanation: The following triplets meet the conditions:
- (0, 2, 4) because 4 != 2 != 3
- (1, 2, 4) because 4 != 2 != 3
- (2, 3, 4) because 2 != 4 != 3
Since there are 3 triplets, we return 3.
Note that (2, 0, 4) is not a valid triplet because 2 > 0.

Example 2

1
2
3

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: No triplets meet the conditions so we return 0.

Constraints

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

Solution

Method 1 – Counting by Frequency

Intuition

We want to count the number of triplets (i, j, k) with i < j < k and all values distinct. Since n is small, we can count the frequency of each unique value, then for each combination of three different values, multiply their frequencies and sum up.

Approach

  1. Count the frequency of each unique value in nums.
  2. For each combination of three distinct values, multiply their frequencies and sum up.
  3. Return the total.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <unordered_map>
class Solution {
public:
    int unequalTriplets(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;
        vector<int> vals;
        for (auto& [k, v] : freq) vals.push_back(v);
        int n = vals.size(), ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i+1; j < n; ++j)
                for (int k = j+1; k < n; ++k)
                    ans += vals[i] * vals[j] * vals[k];
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func unequalTriplets(nums []int) int {
    freq := map[int]int{}
    for _, x := range nums { freq[x]++ }
    vals := []int{}
    for _, v := range freq { vals = append(vals, v) }
    n, ans := len(vals), 0
    for i := 0; i < n; i++ {
        for j := i+1; j < n; j++ {
            for k := j+1; k < n; k++ {
                ans += vals[i] * vals[j] * vals[k]
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
class Solution {
    public int unequalTriplets(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
        List<Integer> vals = new ArrayList<>(freq.values());
        int n = vals.size(), ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                for (int k = j+1; k < n; k++)
                    ans += vals.get(i) * vals.get(j) * vals.get(k);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun unequalTriplets(nums: IntArray): Int {
        val freq = nums.groupingBy { it }.eachCount().values.toList()
        var ans = 0
        val n = freq.size
        for (i in 0 until n)
            for (j in i+1 until n)
                for (k in j+1 until n)
                    ans += freq[i] * freq[j] * freq[k]
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def unequalTriplets(self, nums: list[int]) -> int:
        from collections import Counter
        freq = list(Counter(nums).values())
        ans = 0
        n = len(freq)
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1, n):
                    ans += freq[i] * freq[j] * freq[k]
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

use std::collections::HashMap;
impl Solution {
    pub fn unequal_triplets(nums: Vec<i32>) -> i32 {
        let mut freq = HashMap::new();
        for &x in &nums { *freq.entry(x).or_insert(0) += 1; }
        let vals: Vec<_> = freq.values().cloned().collect();
        let n = vals.len();
        let mut ans = 0;
        for i in 0..n {
            for j in i+1..n {
                for k in j+1..n {
                    ans += vals[i] * vals[j] * vals[k];
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    unequalTriplets(nums: number[]): number {
        const freq = new Map<number, number>()
        for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1)
        const vals = Array.from(freq.values())
        let ans = 0, n = vals.length
        for (let i = 0; i < n; i++)
            for (let j = i+1; j < n; j++)
                for (let k = j+1; k < n; k++)
                    ans += vals[i] * vals[j] * vals[k]
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n^3) (but n ≤ 100, so it’s fast)
  • 🧺 Space complexity: O(n)