We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Unequal Triplets in Array

Number: 2566

Difficulty: Easy

Paid? No

Companies: Amazon, Paytm

Problem Description

Given a 0-indexed array of positive integers, count the number of triplets (i, j, k) with 0 <= i < j < k < nums.length such that the numbers at these indices are pairwise distinct (i.e. no two of nums[i], nums[j], and nums[k] are equal).

Key Insights

  • The problem asks for triplets with distinct values.
  • A direct triple loop is possible given the constraint (n <= 100), but there is a mathematical approach using frequency counts.
  • Use frequency counting: Count how many times each number appears.
  • The total number of triplets from an array of size n is C(n, 3).
  • To obtain only valid triplets, subtract the counts of invalid triplets. There are two invalid cases:
    • Triplets where exactly two numbers are the same: For a number with frequency f, there are C(f, 2) * (n - f) invalid triplets.
    • Triplets where all three numbers are the same: For a number with frequency f, there are C(f, 3) invalid triplets.
  • Then, the valid count is total triplets minus the sum of these invalid ones.

Space and Time Complexity

Time Complexity: O(n + U) where n is the number of elements and U is the number of unique elements.
Space Complexity: O(U) for storing the frequency counts.

Solution

The solution first computes the frequency of each unique number in the array using a hash table. Then, it calculates the total number of triplets possible (using the combination formula C(n, 3)). After that, it subtracts invalid triplets which involve duplicate numbers. This way, only the triplets with pairwise distinct values remain. The approach efficiently uses mathematical combinations and frequency counts to avoid unnecessary repeated comparisons.

Code Solutions

# Python Solution
from collections import Counter

def unequalTriplets(nums):
    # Calculate the total number of elements in the list
    n = len(nums)
    
    # Calculate total possible triplets using combination formula C(n, 3)
    total_triplets = n * (n - 1) * (n - 2) // 6
    
    # Build frequency count for each unique number
    freq = Counter(nums)
    invalid_triplets = 0
    
    # Calculate invalid triplets:
    # Case 1: Two numbers are the same and one is different (C(f, 2) * (n - f))
    # Case 2: All three numbers are the same (C(f, 3))
    for f in freq.values():
        if f >= 2:
            invalid_triplets += (f * (f - 1) // 2) * (n - f)
        if f >= 3:
            invalid_triplets += (f * (f - 1) * (f - 2) // 6)
            
    # Subtract invalid triplets from total triplets to get the valid ones
    return total_triplets - invalid_triplets

# Example usage:
nums = [4, 4, 2, 4, 3]
print(unequalTriplets(nums))  # Expected output: 3
← Back to All Questions