Number of Unequal Triplets in Array — LeetCode 2475 Python Solution

The 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.

Example

Input

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

Output

3

Explanation

The following triplets meet the conditions:

Python solution

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

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2475. Number of Unequal Triplets in Array is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems