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.
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] <= 1000Problem 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.
This approach involves iterating through all possible triplets in the array and checking if they satisfy the given conditions of being pairwise distinct.
The outer loop iterates over the array for the first element, the middle loop for the second and the innermost loop for the third. For every triplet, it checks if all three numbers are distinct.
Time Complexity: O(n^3), where n is the length of the array, since it involves three nested loops.
Space Complexity: O(1) as no additional space is used aside from variables.
This optimized strategy involves using a HashMap to keep track of the frequency of each integer in the array, reducing redundant checks significantly.
This C code uses a frequency array `freq` to store the number of occurrences of each number. For each unique value, it calculates the number of valid triplets it can form using mathematical combinations.
Time Complexity: O(n + m), where n is the length of the array and m is the range of numbers (1000 in constraints), due to counting frequencies and evaluating distinct pairs.
Space Complexity: O(m) for the frequency array.
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).
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.
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.
Rust
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), where n is the length of the array, since it involves three nested loops. |
| Optimized Approach Using HashMap | Time Complexity: O(n + m), where n is the length of the array and m is the range of numbers (1000 in constraints), due to counting frequencies and evaluating distinct pairs. |
| Brute Force Enumeration | — |
| Sorting + Enumeration of Middle Elements + Binary Search | — |
| Hash Table | — |
| Default Approach | — |
| 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 |
Number of Unequal Triplets in Array - Leetcode 2475 - Python • CheatCode Ninja • 1,730 views views
Watch 9 more video solutions →Practice Number of Unequal Triplets in Array with our built-in code editor and test cases.
Practice on FleetCode