Number of Unequal Triplets in Array solution and explanation
9 more videos on this problem
Number of Unequal Triplets in Array - Leetcode 2475 - PythonCheatCode Ninja · 7:33 · 1K views
2475. Number of Unequal Triplets in Array | Weekly 320 | LeetCode 2475Bro Coders · 3:42 · 1K views
Number of Unequal Triplets in Array | leetcode Weekly 320 | Leetcode MediumBinaryMagic · 5:16 · 951 views
2475. Number of Unequal Triplets in Array (Leetcode Easy)Programming Live with Larry · 3:44 · 717 views
Leetcode 2475. Number of Unequal Triplets in ArrayElite Code · 33:01 · 552 views
Leetcode Weekly contest 320 - Easy - Number of Unequal Triplets in ArrayPrakhar Agrawal · 2:46 · 332 views
2475. (Easy) Number of Unequal Triplets in Array (Day 92)yeetcode · 1:55 · 219 views
Number of Unequal Triplets in Array || LeetCode Weekly 320 || Easy || C++Priyanshi Porwal · 4:38 · 202 views
Leetcode 6241 || Number of Unequal Triplets in Array || Leetcode Contest Easy || Array|| CPPCoding Techniques with Komal | Newton School · 2:49 · 121 views
A. NUMBER OF UNEQUAL TRIPLET IN ARRAY - LEETCODE WEEKLY CONTEST 320 (Code + Explanation in details)Joyjit Codes · 1:40 · 713 views
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.lengthnums[i],nums[j], andnums[k]are pairwise distinct.- In other words,
nums[i] != nums[j],nums[i] != nums[k], andnums[j] != nums[k].
- In other words,
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
Approach overview
Problem Overview: Given an integer array nums, count the number of index triplets (i, j, k) such that i < j < k and the values nums[i], nums[j], and nums[k] are all different. The task is to efficiently count all valid combinations without checking unnecessary duplicates.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Check every possible triplet of indices using three nested loops. For each combination (i, j, k), verify that nums[i] != nums[j], nums[i] != nums[k], and nums[j] != nums[k]. If all three values differ, increment the count. This approach directly follows the problem definition and is easy to implement, but the O(n^3) time complexity becomes slow as the array grows. It’s mainly useful as a baseline or for demonstrating correctness before optimization.
Approach 2: Frequency Counting with HashMap (O(n + k) time, O(k) space)
Instead of checking every index triplet, count how many times each value appears using a hash table. Suppose a value appears freq times. Maintain two running counts: elements to the left (left) and elements to the right (right). For each distinct value, the number of triplets where it is the middle group is left * freq * right. Update left as you iterate through unique values and recompute right = n - left - freq. This avoids iterating over indices and instead counts valid combinations using frequencies. The algorithm runs in O(n + k) time where k is the number of distinct values.
Alternative: Sorting + Group Counting (O(n log n) time, O(1) extra space)
Another option is sorting the array first using a standard sorting algorithm. After sorting, identical values appear in contiguous blocks. Compute the size of each block and apply the same combinational idea used in the hash map approach: elements before the block form the left group and elements after form the right group. Sorting introduces O(n log n) time but removes the need for a hash map.
Recommended for interviews: The frequency counting solution using a Hash Table is the expected answer. It reduces the problem from checking index combinations to counting value groups. Mentioning the brute force approach first shows you understand the definition of the triplet constraint, while the optimized counting approach demonstrates strong algorithmic thinking with array frequency analysis.
Approach 1: Brute Force Approach
This approach involves iterating through all possible triplets in the array and checking if they satisfy the given conditions of being pairwise distinct.
def unequalTriplets(nums):
count = 0
n = len(nums)
for i in range(n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
if nums[i] != nums[j] and nums[j] != nums[k] and nums[i] != nums[k]:
count += 1
return count
nums = [4, 4, 2, 4, 3]
print(unequalTriplets(nums)) # Output: 3public class Solution {
public int unequalTriplets(int[] nums) {
int count = 0;
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {4, 4, 2, 4, 3};
System.out.println(sol.unequalTriplets(nums)); // Output: 3
}
}#include <iostream>
#include <vector>
using namespace std;
int unequalTriplets(vector<int>& nums) {
int count = 0;
int n = nums.size();
for(int i = 0; i < n - 2; i++) {
for(int j = i + 1; j < n - 1; j++) {
for(int k = j + 1; k < n; k++) {
if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]) {
count++;
}
}
}
}
return count;
}
int main() {
vector<int> nums = {4, 4, 2, 4, 3};
cout << unequalTriplets(nums) << endl; // Output: 3
return 0;
}function unequalTriplets(nums) {
let count = 0;
const n = nums.length;
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]) {
count++;
}
}
}
}
return count;
}
const nums = [4, 4, 2, 4, 3];
console.log(unequalTriplets(nums)); // Output: 3#include <stdio.h>
int unequalTriplets(int* nums, int numsSize){
int count = 0;
for(int i = 0; i < numsSize - 2; i++) {
for(int j = i + 1; j < numsSize - 1; j++) {
for(int k = j + 1; k < numsSize; k++) {
if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]) {
count++;
}
}
}
}
return count;
}
int main() {
int nums[] = {4, 4, 2, 4, 3};
int length = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", unequalTriplets(nums, length)); // Output: 3
return 0;
}using System;
class Solution {
public int UnequalTriplets(int[] nums) {
int count = 0;
int n = nums.Length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] != nums[j] && nums[j] != nums[k] && nums[i] != nums[k]) {
count++;
}
}
}
}
return count;
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {4, 4, 2, 4, 3};
Console.WriteLine(sol.UnequalTriplets(nums)); // Output: 3
}
}The solution uses three nested loops to examine every possible triplet and checks if each triplet has all distinct elements.
Time Complexity: O(n^3)
Space Complexity: O(1)
Approach 2: Optimized Approach Using HashMap
This optimized strategy involves using a HashMap to keep track of the frequency of each integer in the array, reducing redundant checks significantly.
def unequalTriplets(nums):
from collections import Counter
freq = Counter(nums)
total = 0
prefix_sum = 0
n = len(nums)
for count in freq.values():
total += prefix_sum * count * (n - prefix_sum - count)
prefix_sum += count
return total
nums = [4, 4, 2, 4, 3]
print(unequalTriplets(nums)) # Output: 3import java.util.HashMap;
public class Solution {
public int unequalTriplets(int[] nums) {
HashMap<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int total = 0;
int prefixSum = 0;
for (int count : freq.values()) {
total += prefixSum * count * (nums.length - prefixSum - count);
prefixSum += count;
}
return total;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {4, 4, 2, 4, 3};
System.out.println(sol.unequalTriplets(nums)); // Output: 3
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int unequalTriplets(vector<int>& nums) {
unordered_map<int, int> freq;
for (int num : nums) {
freq[num]++;
}
int total = 0;
int prefixSum = 0;
for (auto& [num, count] : freq) {
total += prefixSum * count * (nums.size() - prefixSum - count);
prefixSum += count;
}
return total;
}
int main() {
vector<int> nums = {4, 4, 2, 4, 3};
cout << unequalTriplets(nums) << endl; // Output: 3
return 0;
}function unequalTriplets(nums) {
const freq = {};
nums.forEach(num => freq[num] = (freq[num] || 0) + 1);
let total = 0;
let prefixSum = 0;
const n = nums.length;
for (const count of Object.values(freq)) {
total += prefixSum * count * (n - prefixSum - count);
prefixSum += count;
}
return total;
}
const nums = [4, 4, 2, 4, 3];
console.log(unequalTriplets(nums)); // Output: 3#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NUM 1000
int unequalTriplets(int* nums, int numsSize){
int freq[MAX_NUM + 1] = {0};
for(int i = 0; i < numsSize; i++) {
freq[nums[i]]++;
}
int total = 0;
int prefixSum = 0;
for(int i = 0; i <= MAX_NUM; i++) {
if(freq[i] > 0) {
total += prefixSum * freq[i] * (numsSize - prefixSum - freq[i]);
prefixSum += freq[i];
}
}
return total;
}
int main() {
int nums[] = {4, 4, 2, 4, 3};
int length = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", unequalTriplets(nums, length)); // Output: 3
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public int UnequalTriplets(int[] nums) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (int num in nums) {
if (!freq.ContainsKey(num)) {
freq[num] = 0;
}
freq[num]++;
}
int total = 0;
int prefixSum = 0;
foreach (var count in freq.Values) {
total += prefixSum * count * (nums.Length - prefixSum - count);
prefixSum += count;
}
return total;
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {4, 4, 2, 4, 3};
Console.WriteLine(sol.UnequalTriplets(nums)); // Output: 3
}
}Python uses `collections.Counter` to track number frequencies, which simplifies counting operations. We compute triplet formations by combining frequency values and prefix sums.
Time Complexity: O(n + m)
Space Complexity: O(m)
Approach 3: 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(n^3), where n is the length of the array nums. The space complexity is O(1).
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;
}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
}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
}
}Approach 4: 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) times (n - k), which is added to the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array nums.
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;
}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
}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
}
}Approach 5: 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 times b times 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.
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
}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
}
}Approach 6: Default Approach
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
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) |
| Optimized Approach Using HashMap | Time Complexity: O(n + m) |
| Brute Force Enumeration | – |
| Sorting + Enumeration of Middle Elements + Binary Search | – |
| Hash Table | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triple Loop | O(n^3) | O(1) | Small arrays or for understanding the basic triplet condition |
| HashMap Frequency Counting | O(n + k) | O(k) | Best general solution when the array is unsorted and you want linear time |
| Sorting + Group Counting | O(n log n) | O(1) | When sorting is acceptable or memory usage must stay minimal |
Frequently asked questions
Is Number of Unequal Triplets in Array easy or hard?
LeetCode classifies this problem as Easy. The brute force solution is straightforward, but the intended optimization introduces a common interview pattern: counting combinations using frequency maps to avoid unnecessary nested loops.
Number of Unequal Triplets in Array Python/Java solution
In Python or Java, the common solution builds a frequency map using a dictionary or HashMap. Then iterate through the map while maintaining counts of elements to the left and right to compute left * freq * right. This approach runs in O(n) time and is concise in both languages.
How to solve Number of Unequal Triplets in Array in O(n)?
Count the frequency of each number using a hash map. Iterate through the distinct values while tracking how many elements are on the left and right of the current value group. The number of valid triplets formed with that group is left * freq * right. Summing these counts produces the answer in linear time.
What is the best approach for Number of Unequal Triplets in Array?
The best approach uses frequency counting with a hash map. First count how many times each number appears, then compute combinations using leftCount * freq * rightCount for each unique value group. This avoids checking every index triplet and runs in O(n + k) time where k is the number of distinct values.
Is Number of Unequal Triplets in Array asked at Google/Amazon/Meta?
Triplet counting and frequency-based array problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations often test whether you can reduce nested loops by grouping elements with a hash map or sorting strategy.
What data structure is used in Number of Unequal Triplets in Array?
The optimized solution uses a hash map (or dictionary) to store frequencies of each number. This allows constant-time lookups and enables counting combinations of distinct value groups instead of iterating over index triplets.
What is the time complexity of Number of Unequal Triplets in Array?
The brute force method takes O(n^3) time because it checks every possible triplet of indices. The optimized frequency counting approach runs in O(n + k) time and O(k) space, where k is the number of unique elements. A sorting-based alternative runs in O(n log n).