Problem Description

You are given an array of positive integers nums that is 0-indexed. Your task is to count how many triplets of indices (i, j, k) satisfy specific conditions.

For a valid triplet (i, j, k), the following must be true:

1. Index ordering: The indices must be in strictly increasing order, meaning 0 <= i < j < k < nums.length. This ensures we're selecting three different positions from the array.

2. Pairwise distinct values: The values at these three positions must all be different from each other. Specifically:

   • nums[i] != nums[j] (first and second values are different)
   • nums[i] != nums[k] (first and third values are different)
   • nums[j] != nums[k] (second and third values are different)

The solution uses a brute force approach with three nested loops to check every possible combination of three indices. For each combination where i < j < k, it checks if all three values are different from each other. If they are, it increments the count. The time complexity is O(n³) where n is the length of the array, as we examine all possible triplets.

For example, if nums = [4, 4, 2, 4, 3], valid triplets would include (0, 2, 4) because nums[0] = 4, nums[2] = 2, and nums[4] = 3 are all different from each other.

Intuition

When we need to find all valid triplets from an array, the most straightforward approach is to examine every possible combination of three elements. Since we need to check specific conditions for each triplet, we can systematically generate all possible triplets and verify if they meet our requirements.

The key insight is that we need three distinct positions i < j < k, and for each such triplet of positions, we need to check if the values at these positions are all different. This naturally leads to a three-level nested loop structure:

• The outer loop picks the first position i
• The middle loop picks the second position j (starting from i + 1 to ensure j > i)
• The inner loop picks the third position k (starting from j + 1 to ensure k > j)

This way, we automatically satisfy the ordering constraint i < j < k through our loop structure. For each generated triplet, we then only need to verify that the three values are pairwise distinct.

The brute force approach works well here because:

1. We need to examine relationships between three elements, which inherently requires looking at combinations
2. The constraint checking is simple - just comparing three values for inequality
3. There's no obvious pattern or mathematical property that would allow us to count valid triplets without examining them

We could optimize this further by using frequency counting or other techniques, but the brute force solution is clear, correct, and easy to implement. It directly translates the problem requirements into code: generate all ordered triplets and count those where all three values are different.

Learn more about Sorting patterns.

Solution Approach

The implementation uses a brute force enumeration approach with three nested loops to check all possible triplets.

Algorithm Steps:

1. Initialize counter: Start with ans = 0 to keep track of valid triplets.

2. Triple nested loops:

   • First loop: for i in range(n) - iterates through all possible first positions
   • Second loop: for j in range(i + 1, n) - iterates through all positions after i
   • Third loop: for k in range(j + 1, n) - iterates through all positions after j

3. Condition checking: For each triplet (i, j, k), check if all three values are pairwise distinct:

   nums[i] != nums[j] and nums[j] != nums[k] and nums[i] != nums[k]

4. Count valid triplets: The expression in step 3 evaluates to True (which equals 1) when all conditions are met, or False (which equals 0) otherwise. Adding this boolean result to ans effectively counts the valid triplets:

   ans += (nums[i] != nums[j] and nums[j] != nums[k] and nums[i] != nums[k])

Key Implementation Details:

• The loop structure i < j < k is maintained by starting each inner loop from the previous index + 1
• Python's boolean-to-integer conversion is utilized: True becomes 1 and False becomes 0 when added to an integer
• No additional data structures are needed - just the counter variable ans
• Time complexity: O(n³) as we examine all C(n, 3) possible triplets
• Space complexity: O(1) as we only use a constant amount of extra space

This straightforward implementation directly translates the problem requirements into code without any optimization tricks, making it easy to understand and verify for correctness.

Example Walkthrough

Let's walk through the solution with nums = [1, 3, 1, 5, 4].

We need to find all triplets (i, j, k) where i < j < k and the values at these positions are all different.

Step-by-step execution:

Iteration 1: i = 0 (nums[0] = 1)

• j = 1, k = 2: Check (0, 1, 2) → nums[0]=1, nums[1]=3, nums[2]=1 → 1≠3 ✓, 3≠1 ✓, but 1=1 ✗ → Not valid
• j = 1, k = 3: Check (0, 1, 3) → nums[0]=1, nums[1]=3, nums[3]=5 → 1≠3 ✓, 3≠5 ✓, 1≠5 ✓ → Valid! Count = 1
• j = 1, k = 4: Check (0, 1, 4) → nums[0]=1, nums[1]=3, nums[4]=4 → 1≠3 ✓, 3≠4 ✓, 1≠4 ✓ → Valid! Count = 2
• j = 2, k = 3: Check (0, 2, 3) → nums[0]=1, nums[2]=1, nums[3]=5 → 1=1 ✗ → Not valid
• j = 2, k = 4: Check (0, 2, 4) → nums[0]=1, nums[2]=1, nums[4]=4 → 1=1 ✗ → Not valid
• j = 3, k = 4: Check (0, 3, 4) → nums[0]=1, nums[3]=5, nums[4]=4 → 1≠5 ✓, 5≠4 ✓, 1≠4 ✓ → Valid! Count = 3

Iteration 2: i = 1 (nums[1] = 3)

• j = 2, k = 3: Check (1, 2, 3) → nums[1]=3, nums[2]=1, nums[3]=5 → 3≠1 ✓, 1≠5 ✓, 3≠5 ✓ → Valid! Count = 4
• j = 2, k = 4: Check (1, 2, 4) → nums[1]=3, nums[2]=1, nums[4]=4 → 3≠1 ✓, 1≠4 ✓, 3≠4 ✓ → Valid! Count = 5
• j = 3, k = 4: Check (1, 3, 4) → nums[1]=3, nums[3]=5, nums[4]=4 → 3≠5 ✓, 5≠4 ✓, 3≠4 ✓ → Valid! Count = 6

Iteration 3: i = 2 (nums[2] = 1)

• j = 3, k = 4: Check (2, 3, 4) → nums[2]=1, nums[3]=5, nums[4]=4 → 1≠5 ✓, 5≠4 ✓, 1≠4 ✓ → Valid! Count = 7

Iteration 4: i = 3 (nums[3] = 5)

• No valid j exists since j must be < 4 and k must be < 5 (array length)

Final Result: 7 valid triplets

The algorithm systematically checks all possible combinations where indices increase (i < j < k) and counts those where all three values differ. The three nested loops ensure we examine every possible triplet exactly once.

Solution Implementation

Time and Space Complexity

The time complexity is O(n³), where n is the length of the array nums. This is because the code uses three nested loops: the outer loop runs n times, the middle loop runs up to n-1 times for each iteration of the outer loop, and the inner loop runs up to n-2 times for each iteration of the middle loop. In the worst case, this results in approximately n * (n-1) * (n-2) / 6 iterations, which simplifies to O(n³).

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the variables n, ans, i, j, and k, regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Index Range in Nested Loops

A common mistake is setting up the loop ranges incorrectly, which can lead to either missing valid triplets or counting duplicates.

Incorrect Implementation:

# Wrong: Using wrong starting points
for i in range(n):
    for j in range(n):  # Should start from i+1
        for k in range(n):  # Should start from j+1
            if i < j < k and nums[i] != nums[j] != nums[k]:
                count += 1

Problem: This wastes iterations checking invalid index combinations and requires additional logic to ensure i < j < k.

Correct Approach:

for i in range(n):
    for j in range(i + 1, n):  # Start from i+1
        for k in range(j + 1, n):  # Start from j+1
            # No need to check i < j < k since it's guaranteed by loop structure

2. Incorrect Pairwise Comparison Logic

Another frequent error is using chained inequality operators incorrectly for checking distinctness.

Incorrect Implementation:

# Wrong: This doesn't check all pairwise differences
if nums[i] != nums[j] != nums[k]:
    count += 1

Problem: The expression nums[i] != nums[j] != nums[k] in Python means (nums[i] != nums[j]) and (nums[j] != nums[k]). This doesn't check if nums[i] != nums[k]. For example, if nums[i] = 1, nums[j] = 2, nums[k] = 1, the condition would pass even though nums[i] == nums[k].

Correct Approach:

# Explicitly check all three pairs
if nums[i] != nums[j] and nums[j] != nums[k] and nums[i] != nums[k]:
    count += 1

3. Off-by-One Errors in Loop Bounds

Incorrect Implementation:

# Wrong: Missing the last element
for i in range(n-2):
    for j in range(i + 1, n-1):
        for k in range(j + 1, n):

Problem: The first loop should go up to n-2 (inclusive) since we need at least 3 elements, but writing range(n-3) would miss valid triplets.

Correct Approach:

# Can use full range and let inner loops handle bounds
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
# Or optimize slightly:
for i in range(n - 2):  # Stop when less than 3 elements remain
    for j in range(i + 1, n - 1):  # Stop when less than 2 elements remain
        for k in range(j + 1, n):

4. Performance Consideration for Large Arrays

While not a logical error, using the O(n³) brute force approach on large arrays can cause timeouts.

Alternative Optimization Using Frequency Count:

def unequalTriplets(self, nums: List[int]) -> int:
    from collections import Counter
    freq = Counter(nums)
  
    if len(freq) < 3:
        return 0
  
    result = 0
    prev = 0
    next_count = len(nums)
  
    for count in freq.values():
        next_count -= count
        result += prev * count * next_count
        prev += count
  
    return result

This optimized solution runs in O(n) time by counting frequencies and calculating combinations mathematically.