Number of Unequal Triplets in Array

EASY

Description

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

Checkout 3 different approaches to solve Number of Unequal Triplets in Array. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Iteration

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a constant amount of extra space for the counter and loop variables.

Pros and Cons

Pros:

Simple to understand and implement.
Requires no extra space.

Cons:

Highly inefficient for larger input arrays, although it passes within the given constraints.

Code Solutions

Checking out 3 solutions in different languages for Number of Unequal Triplets in Array. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Number of Unequal Triplets in Array

Algorithms:

Sorting

Data Structures:

ArrayHash Table

Companies:

Paytm |