Skip to main content
Talentd

Number of Unequal Triplets in Array - Solution & Explanation

EasyArrayHash TableSorting23 min readAsked at: Paytm
Practice this problem

Problem Statement

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], 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 <= 100
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

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.

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Approach 6: Default Approach

Code

Rust

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

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.

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.
Space Complexity: O(m) for the frequency array.

Brute Force Enumeration—
Sorting + Enumeration of Middle Elements + Binary Search—
Hash Table—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triple LoopO(n^3)O(1)Small arrays or for understanding the basic triplet condition
HashMap Frequency CountingO(n + k)O(k)Best general solution when the array is unsorted and you want linear time
Sorting + Group CountingO(n log n)O(1)When sorting is acceptable or memory usage must stay minimal

Video Solution

Number of Unequal Triplets in Array - Leetcode 2475 - Python • CheatCode Ninja • 1,808 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Number of Unequal Triplets in Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Good Triplets

Next

Count Square Sum Triples