Description
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.lengthnums[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 <= 1001 <= nums[i] <= 1000
Solutions
Solution 1: Brute Force Enumeration
We can directly enumerate all triples (i, j, k) and count all the ones that meet the conditions.
The time complexity is O(n3), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRust
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
func unequalTriplets(nums []int) (ans int) {
n := len(nums)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
if nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k] {
ans++
}
}
}
}
return
}(code-box)
function unequalTriplets(nums: number[]): number {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; k++) {
if (nums[i] !== nums[j] && nums[j] !== nums[k] && nums[i] !== nums[k]) {
ans++;
}
}
}
}
return ans;
}(code-box)
impl Solution {
pub fn unequal_triplets(nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut ans = 0;
for i in 0..n - 2 {
for j in i + 1..n - 1 {
for k in j + 1..n {
if nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k] {
ans += 1;
}
}
}
}
ans
}
}(code-box)
Solution 2: Sorting + Enumeration of Middle Elements + Binary Search
We can also sort the array nums first.
Then traverse nums, enumerate the middle element nums[j], and use binary search to find the nearest index i on the left side of nums[j] such that nums[i] < nums[j]; find the nearest index k on the right side of nums[j] such that nums[k] > nums[j]. Then the number of triples with nums[j] as the middle element and meeting the conditions is (i + 1) × (n - k), which is added to the answer.
The time complexity is O(n × log n), and the space complexity is O(log n). Here, n is the length of the array nums.
PythonJavaC++GoTypeScriptRust
class Solution:
def unequalTriplets(self, nums: List[int]) -> int:
nums.sort()
ans, n = 0, len(nums)
for j in range(1, n - 1):
i = bisect_left(nums, nums[j], hi=j) - 1
k = bisect_right(nums, nums[j], lo=j + 1)
ans += (i >= 0 and k < n) * (i + 1) * (n - k)
return ans(code-box)
class Solution {
public int unequalTriplets(int[] nums) {
Arrays.sort(nums);
int ans = 0, n = nums.length;
for (int j = 1; j < n - 1; ++j) {
int i = search(nums, nums[j], 0, j) - 1;
int k = search(nums, nums[j] + 1, j + 1, n);
if (i >= 0 && k < n) {
ans += (i + 1) * (n - k);
}
}
return ans;
}
private int search(int[] nums, int x, int left, int right) {
while (left < right) {
int mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}(code-box)
class Solution {
public:
int unequalTriplets(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0, n = nums.size();
for (int j = 1; j < n - 1; ++j) {
int i = lower_bound(nums.begin(), nums.begin() + j, nums[j]) - nums.begin() - 1;
int k = upper_bound(nums.begin() + j + 1, nums.end(), nums[j]) - nums.begin();
if (i >= 0 && k < n) {
ans += (i + 1) * (n - k);
}
}
return ans;
}
};(code-box)
func unequalTriplets(nums []int) (ans int) {
sort.Ints(nums)
n := len(nums)
for j := 1; j < n-1; j++ {
i := sort.Search(j, func(h int) bool { return nums[h] >= nums[j] }) - 1
k := sort.Search(n, func(h int) bool { return h > j && nums[h] > nums[j] })
if i >= 0 && k < n {
ans += (i + 1) * (n - k)
}
}
return
}(code-box)
function unequalTriplets(nums: number[]): number {
const n = nums.length;
const cnt = new Map<number, number>();
for (const num of nums) {
cnt.set(num, (cnt.get(num) ?? 0) + 1);
}
let ans = 0;
let a = 0;
for (const b of cnt.values()) {
const c = n - a - b;
ans += a * b * c;
a += b;
}
return ans;
}(code-box)
use std::collections::HashMap;
impl Solution {
pub fn unequal_triplets(nums: Vec<i32>) -> i32 {
let mut cnt = HashMap::new();
for num in nums.iter() {
*cnt.entry(num).or_insert(0) += 1;
}
let n = nums.len();
let mut ans = 0;
let mut a = 0;
for v in cnt.values() {
let b = n - a - v;
ans += v * a * b;
a += v;
}
ans as i32
}
}(code-box)
Solution 3: Hash Table
We can also use a hash table cnt to count the number of each element in the array nums.
Then traverse the hash table cnt, enumerate the number of middle elements b, and denote the number of elements on the left as a. Then the number of elements on the right is c = n - a - b. At this time, the number of triples that meet the conditions is a × b × c, which is added to the answer. Then update a = a + b and continue to enumerate the number of middle elements b.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
PythonJavaC++GoRust
class Solution:
def unequalTriplets(self, nums: List[int]) -> int:
cnt = Counter(nums)
n = len(nums)
ans = a = 0
for b in cnt.values():
c = n - a - b
ans += a * b * c
a += b
return ans(code-box)
class Solution {
public int unequalTriplets(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int v : nums) {
cnt.merge(v, 1, Integer::sum);
}
int ans = 0, a = 0;
int n = nums.length;
for (int b : cnt.values()) {
int c = n - a - b;
ans += a * b * c;
a += b;
}
return ans;
}
}(code-box)
class Solution {
public:
int unequalTriplets(vector<int>& nums) {
unordered_map<int, int> cnt;
for (int& v : nums) {
++cnt[v];
}
int ans = 0, a = 0;
int n = nums.size();
for (auto& [_, b] : cnt) {
int c = n - a - b;
ans += a * b * c;
a += b;
}
return ans;
}
};(code-box)
func unequalTriplets(nums []int) (ans int) {
cnt := map[int]int{}
for _, v := range nums {
cnt[v]++
}
a, n := 0, len(nums)
for _, b := range cnt {
c := n - a - b
ans += a * b * c
a += b
}
return
}(code-box)
use std::collections::HashMap;
impl Solution {
pub fn unequal_triplets(nums: Vec<i32>) -> i32 {
let cnt = nums.iter().fold(HashMap::new(), |mut map, &n| {
*map.entry(n).or_insert(0) += 1;
map
});
let mut ans = 0;
let n = nums.len();
let mut a = 0;
for &b in cnt.values() {
let c = n - a - b;
ans += a * b * c;
a += b;
}
ans as i32
}
}(code-box)
Solution 4
Rust
impl Solution {
pub fn unequal_triplets(nums: Vec<i32>) -> i32 {
let mut ans = 0;
let mut nums = nums;
nums.sort();
let n = nums.len();
for i in 1..n - 1 {
let mut l = 0;
let mut r = i;
while l < r {
let mid = (l + r) >> 1;
if nums[mid] >= nums[i] {
r = mid;
} else {
l = mid + 1;
}
}
let j = r;
let mut l = i + 1;
let mut r = n;
while l < r {
let mid = (l + r) >> 1;
if nums[mid] > nums[i] {
r = mid;
} else {
l = mid + 1;
}
}
let k = r;
ans += j * (n - k);
}
ans as i32
}
}(code-box)
