Scale Engineer

Number of Unequal Triplets in Array

Easy
#2258Time: 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.1 company
Algorithms
Sorting
Data structures
ArrayHash Table
Companies
Paytm

Prompt

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

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 count to 0.
  • Get the length of the array, n.
  • Use a for loop to iterate with index i from 0 to n-3.
  • Inside, use a nested for loop for index j from i+1 to n-2.
  • Inside, use another nested for loop for index k from j+1 to n-1.
  • In the innermost loop, check if the triplet of values is pairwise distinct: nums[i] != nums[j], nums[i] != nums[k], and nums[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.

Solutions

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;  }}

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

← Previous

Previous problem

Next →

Next problem