#2475

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Unequal Triplets in Array

Count all triplets in a positive integer array where each element is distinct using scanning and hash lookup efficiently.

array hash table sorting

Problem Statement

Given a 0-indexed array of positive integers nums, find the number of triplets (i, j, k) such that 0 <= i < j < k < nums.length and nums[i], nums[j], nums[k] are all distinct. Each triplet must maintain the original order in the array.

Return the total number of triplets that meet these conditions. For example, given nums = [4,4,2,4,3], there are 3 valid triplets: (0,2,4), (1,2,4), and (2,3,4). If no triplets meet the criteria, return 0.

Examples

Example 1

Input: nums = [4,4,2,4,3]

Output: 3

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

No triplets meet the conditions so we return 0.

Constraints

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

Solution Approach

Brute Force Triplet Scan

Iterate through all index triples (i,j,k) with i<j<k and check if nums[i], nums[j], nums[k] are all distinct. Count each valid triplet. This works because nums.length is at most 100.

Hash Map Frequency Count

Use a hash map to count occurrences of each number. Then, scan the array and for each pair of indices, use the hash map to find valid third elements. This reduces redundant comparisons and leverages the problem's small input size.

Optimized Array Scanning

Scan the array once to track previous counts and remaining counts. For each middle element, compute how many valid preceding and succeeding elements exist to form distinct triplets. This method ensures O(n^2) complexity while avoiding unnecessary checks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity ranges from O(n^3) for brute force to O(n^2) with hash-based optimizations due to the nested loops. Space complexity is O(n) for frequency maps and auxiliary counters.

What Interviewers Usually Probe

Check if candidate triplets maintain array order and are distinct.
Notice that constraints are small enough to allow nested loops.
Consider hash map usage to avoid repeated comparisons.

Common Pitfalls or Variants

Common pitfalls

Counting triplets that repeat numbers or ignore order.
Mismanaging hash counts leading to overcounting.
Assuming all three numbers are unique globally rather than per triplet.

Follow-up variants

Count triplets with at least two distinct numbers instead of all distinct.
Find unequal quadruplets using a similar scanning plus hash approach.
Compute the sum of all distinct triplets instead of just counting them.

FAQ

What is the main approach for Number of Unequal Triplets in Array?

Use array scanning combined with hash lookup to efficiently count all triplets where elements are distinct and maintain original order.

Can I use brute force for this problem?

Yes, because nums.length <= 100, a triple nested loop is acceptable though hash-based counting is more efficient.

How do I avoid overcounting duplicate numbers?

Track frequency of each number with a hash map and ensure each triplet uses indices in increasing order with all elements distinct.

Does sorting the array help?

Sorting is optional; the core pattern relies on scanning and hash lookup rather than reordering elements.

What if all numbers in nums are the same?

Then no triplets are valid, and the function should return 0.

terminal

Solution

Solution 1: Brute Force Enumeration

We can directly enumerate all triples $(i, j, k)$ and count all the ones that meet the conditions.

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

Solution 2: Sorting + Enumeration of Middle Elements + Binary Search

We can also sort the array $nums$ first.

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

Solution 3: Hash Table

We can also use a hash table $cnt$ to count the number of each element in the array $nums$.

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

Solution 4

#### Rust

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

Continue Practicing

#2465 number of distinct averages #2491 divide players into teams of equal skill #2456 most popular video creator