# Number of Unequal Triplets in Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-unequal-triplets-in-array)
Canonical: https://scaleengineer.com/dsa/problems/number-of-unequal-triplets-in-array
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Paytm](https://scaleengineer.com/companies/paytm)
---
## 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._

**Example 1:**

**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:**

**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`

# Approaches
## Brute-Force Iteration
The most straightforward way to solve this problem is to check every possible triplet of indices `(i, j, k)` that satisfies the condition `0 <= i < j < k < nums.length`.
**Time:** O(n^3), where `n` is the length of the `nums` array. The three nested loops lead to a cubic time complexity. Given the constraint `n <= 100`, this is acceptable. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop variables.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Highly inefficient for larger input arrays, although it passes within the given constraints.
### Explanation
We can use three nested loops to generate all valid index triplets. The outer loop iterates `i` from `0` to `n-3`, the middle loop iterates `j` from `i+1` to `n-2`, and the inner loop iterates `k` from `j+1` to `n-1`. Inside the innermost loop, we check if the values `nums[i]`, `nums[j]`, and `nums[k]` are all different from each other. If they are, we increment a counter. After checking all triplets, the counter will hold the total number of unequal triplets.

```java
class Solution {
    public int unequalTriplets(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Get the length of the array, `n`.
- Use a `for` loop to iterate with index `i` from `0` to `n-3`.
- Inside, use a nested `for` loop for index `j` from `i+1` to `n-2`.
- Inside, use another nested `for` loop for index `k` from `j+1` to `n-1`.
- In the innermost loop, check if the triplet of values is pairwise distinct: `nums[i] != nums[j]`, `nums[i] != nums[k]`, and `nums[j] != nums[k]`.
- If the condition is true, increment `count`.
- After the loops complete, return `count`.

## Frequency Map with Combinations
A more optimized approach involves first counting the occurrences of each number and then calculating the number of triplets based on these counts. This avoids redundant checks for the same numbers.
**Time:** O(n + m^3), where `n` is the length of `nums` and `m` is the number of unique elements. O(n) to build the frequency map and O(m^3) to iterate through combinations of unique numbers. This is faster than O(n^3) when `m` is significantly smaller than `n`. · **Space:** O(m), where `m` is the number of unique elements, to store the frequency map. In the worst case, where all elements are unique, this is O(n).
**Pros:** More efficient than brute-force when there are many duplicate numbers.
**Cons:** The complexity is still cubic in the number of unique elements, which can be as large as `n` in the worst case.; Requires extra space for the frequency map.
### Explanation
First, we iterate through the input array `nums` to build a frequency map (e.g., a HashMap) that stores each unique number and its count. Then, we can form triplets by choosing three *distinct* numbers from our set of unique numbers. We iterate through all combinations of three unique numbers. For each combination of three distinct numbers, say `num1`, `num2`, and `num3`, with counts `c1`, `c2`, and `c3` respectively, the number of triplets we can form is `c1 * c2 * c3`. We sum these products for all combinations of three unique numbers to get the total count.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int unequalTriplets(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        if (counts.size() < 3) {
            return 0;
        }

        List<Integer> uniqueNums = new ArrayList<>(counts.keySet());
        int triplets = 0;
        int m = uniqueNums.size();

        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                for (int k = j + 1; k < m; k++) {
                    int num1 = uniqueNums.get(i);
                    int num2 = uniqueNums.get(j);
                    int num3 = uniqueNums.get(k);
                    triplets += counts.get(num1) * counts.get(num2) * counts.get(num3);
                }
            }
        }
        return triplets;
    }
}
```
### Algorithm
- Create a `HashMap` to store the frequency of each number in `nums`.
- Iterate through `nums` and populate the frequency map.
- If the number of unique elements is less than 3, return 0.
- Extract the unique numbers (keys of the map) into a list.
- Initialize `triplets = 0`.
- Use three nested loops to iterate through all combinations of three distinct unique numbers from the list.
- For each combination `(num1, num2, num3)`, get their counts `c1`, `c2`, `c3` from the map.
- Add the product `c1 * c2 * c3` to `triplets`.
- Return `triplets`.

## Linear Time Solution with Frequency Map
The most efficient approach also uses a frequency map but calculates the result in a single pass over the unique numbers, achieving linear time complexity.
**Time:** O(n), where `n` is the length of `nums`. It takes O(n) to build the frequency map and O(m) to iterate through the unique counts, where `m` is the number of unique elements (`m <= n`). The total time is dominated by the initial pass, making it O(n). · **Space:** O(m), where `m` is the number of unique elements, to store the frequency map. In the worst case, this is O(n).
**Pros:** Highly efficient with linear time complexity.; Conceptually elegant and concise.
**Cons:** Requires extra space for the frequency map.
### Explanation
This method is based on a combinatorial insight. First, we compute the frequency of each number, similar to the previous approach. Then, we can iterate through the unique numbers (or their counts) and for each number, consider it as the middle element of a triplet `(i, j, k)`.
Let's maintain a count of elements we have processed so far (`left`) and the count of elements yet to be processed (`right`). We initialize `left = 0` and `right = n` (total elements).
We iterate through the counts of each unique number. For a unique number with count `c`:
1. The number of elements to the "right" (yet to be processed) is `right - c`.
2. The number of triplets that can be formed with this number as the middle element, one element from the "left" group, and one from the "right" group is `left * c * (right - c)`. We add this to our total.
3. We then update our counters for the next iteration: `left` increases by `c`, and `right` decreases by `c`.
By iterating through all unique number counts, we sum up all possible valid triplets.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int unequalTriplets(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        int n = nums.length;
        int triplets = 0;
        int left = 0;
        int right = n;

        for (int count : counts.values()) {
            right -= count;
            triplets += left * count * right;
            left += count;
        }

        return triplets;
    }
}
```
### Algorithm
- Create a `HashMap` to store the frequency of each number in `nums`.
- Iterate through `nums` and populate the frequency map.
- Initialize `triplets = 0`, `left = 0`, and `right = nums.length`.
- Iterate through the values (counts) in the frequency map. For each `count`:
  - Decrement `right` by `count`.
  - Add the product `left * count * right` to `triplets`.
  - Increment `left` by `count`.
- Return `triplets`.

# Solutions
### Java

```java
class Solution {
public
  int unequalTriplets(int[] nums) {
    int n = nums.length;
    int 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) {
          if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]) {
            ++ans;
          }
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int unequalTriplets(vector<int> &nums) {
    int n = nums.size();
    int 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) {
          if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]) {
            ++ans;
          }
        }
      }
    }
    return ans;
  }
};

```

### Python

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

```