Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2475.html
2475. Number of Unequal Triplets in Array
- Difficulty: Easy.
- Related Topics: .
- Similar Questions: Count Good Triplets, Count Square Sum Triples, Number of Arithmetic Triplets.
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]
, andnums[k]
are pairwise distinct. -
In other words,
nums[i] != nums[j]
,nums[i] != nums[k]
, andnums[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
Solution (Java, C++, Python)
-
class Solution { public int unequalTriplets(int[] nums) { Map<Integer, Integer> cnt = new HashMap<>(); for (int v : nums) { cnt.put(v, cnt.getOrDefault(v, 0) + 1); } 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; } }
-
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; } };
-
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
-
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 }
-
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; }
-
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 } }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).