Number of Unequal Triplets in Array
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward way to solve this problem is to check every possible triplet of indices (i, j, k) that satisfies the condition 0 <= i < j < k < nums.length.
Algorithm
- Initialize a counter
countto 0. - Get the length of the array,
n. - Use a
forloop to iterate with indexifrom0ton-3. - Inside, use a nested
forloop for indexjfromi+1ton-2. - Inside, use another nested
forloop for indexkfromj+1ton-1. - In the innermost loop, check if the triplet of values is pairwise distinct:
nums[i] != nums[j],nums[i] != nums[k], andnums[j] != nums[k]. - If the condition is true, increment
count. - After the loops complete, return
count.
Walkthrough
We can use three nested loops to generate all valid index triplets. The outer loop iterates i from 0 to n-3, the middle loop iterates j from i+1 to n-2, and the inner loop iterates k from j+1 to n-1. Inside the innermost loop, we check if the values nums[i], nums[j], and nums[k] are all different from each other. If they are, we increment a counter. After checking all triplets, the counter will hold the total number of unequal triplets.
class Solution { public int unequalTriplets(int[] nums) { int n = nums.length; int count = 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[i] != nums[k] && nums[j] != nums[k]) { count++; } } } } return count; }}Complexity
Time
O(n^3), where `n` is the length of the `nums` array. The three nested loops lead to a cubic time complexity. Given the constraint `n <= 100`, this is acceptable.
Space
O(1), as we only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Highly inefficient for larger input arrays, although it passes within the given constraints.
A more optimized approach involves first counting the occurrences of each number and then calculating the number of triplets based on these counts. This avoids redundant checks for the same numbers.
Algorithm
- Create a
HashMapto store the frequency of each number innums. - Iterate through
numsand populate the frequency map. - If the number of unique elements is less than 3, return 0.
- Extract the unique numbers (keys of the map) into a list.
- Initialize
triplets = 0. - Use three nested loops to iterate through all combinations of three distinct unique numbers from the list.
- For each combination
(num1, num2, num3), get their countsc1,c2,c3from the map. - Add the product
c1 * c2 * c3totriplets. - Return
triplets.
Walkthrough
First, we iterate through the input array nums to build a frequency map (e.g., a HashMap) that stores each unique number and its count. Then, we can form triplets by choosing three distinct numbers from our set of unique numbers. We iterate through all combinations of three unique numbers. For each combination of three distinct numbers, say num1, num2, and num3, with counts c1, c2, and c3 respectively, the number of triplets we can form is c1 * c2 * c3. We sum these products for all combinations of three unique numbers to get the total count.
import java.util.HashMap;import java.util.Map;import java.util.ArrayList;import java.util.List; class Solution { public int unequalTriplets(int[] nums) { Map<Integer, Integer> counts = new HashMap<>(); for (int num : nums) { counts.put(num, counts.getOrDefault(num, 0) + 1); } if (counts.size() < 3) { return 0; } List<Integer> uniqueNums = new ArrayList<>(counts.keySet()); int triplets = 0; int m = uniqueNums.size(); for (int i = 0; i < m; i++) { for (int j = i + 1; j < m; j++) { for (int k = j + 1; k < m; k++) { int num1 = uniqueNums.get(i); int num2 = uniqueNums.get(j); int num3 = uniqueNums.get(k); triplets += counts.get(num1) * counts.get(num2) * counts.get(num3); } } } return triplets; }}Complexity
Time
O(n + m^3), where `n` is the length of `nums` and `m` is the number of unique elements. O(n) to build the frequency map and O(m^3) to iterate through combinations of unique numbers. This is faster than O(n^3) when `m` is significantly smaller than `n`.
Space
O(m), where `m` is the number of unique elements, to store the frequency map. In the worst case, where all elements are unique, this is O(n).
Trade-offs
Pros
More efficient than brute-force when there are many duplicate numbers.
Cons
The complexity is still cubic in the number of unique elements, which can be as large as
nin the worst case.Requires extra space for the frequency map.
The most efficient approach also uses a frequency map but calculates the result in a single pass over the unique numbers, achieving linear time complexity.
Algorithm
- Create a
HashMapto store the frequency of each number innums. - Iterate through
numsand populate the frequency map. - Initialize
triplets = 0,left = 0, andright = nums.length. - Iterate through the values (counts) in the frequency map. For each
count:- Decrement
rightbycount. - Add the product
left * count * righttotriplets. - Increment
leftbycount.
- Decrement
- Return
triplets.
Walkthrough
This method is based on a combinatorial insight. First, we compute the frequency of each number, similar to the previous approach. Then, we can iterate through the unique numbers (or their counts) and for each number, consider it as the middle element of a triplet (i, j, k).
Let's maintain a count of elements we have processed so far (left) and the count of elements yet to be processed (right). We initialize left = 0 and right = n (total elements).
We iterate through the counts of each unique number. For a unique number with count c:
- The number of elements to the "right" (yet to be processed) is
right - c. - The number of triplets that can be formed with this number as the middle element, one element from the "left" group, and one from the "right" group is
left * c * (right - c). We add this to our total. - We then update our counters for the next iteration:
leftincreases byc, andrightdecreases byc. By iterating through all unique number counts, we sum up all possible valid triplets.
import java.util.HashMap;import java.util.Map; class Solution { public int unequalTriplets(int[] nums) { Map<Integer, Integer> counts = new HashMap<>(); for (int num : nums) { counts.put(num, counts.getOrDefault(num, 0) + 1); } int n = nums.length; int triplets = 0; int left = 0; int right = n; for (int count : counts.values()) { right -= count; triplets += left * count * right; left += count; } return triplets; }}Complexity
Time
O(n), where `n` is the length of `nums`. It takes O(n) to build the frequency map and O(m) to iterate through the unique counts, where `m` is the number of unique elements (`m <= n`). The total time is dominated by the initial pass, making it O(n).
Space
O(m), where `m` is the number of unique elements, to store the frequency map. In the worst case, this is O(n).
Trade-offs
Pros
Highly efficient with linear time complexity.
Conceptually elegant and concise.
Cons
Requires extra space for the frequency map.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.