Jobs

Interviews

Discussions

Number of Unequal Triplets in Array

Easy

Asked by:

12 views

Topics:

Arrays

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

Try coding it in LeetCode

Number of Unequal Triplets in Array

Easy

Asked by:

12 views

Topics:

Arrays

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array? Are there any constraints on memory usage?
Can the integers in the array be negative, zero, or are they strictly positive?
Are duplicate values allowed within the input array, and if so, how should they be handled when forming triplets?
If no unequal triplets exist in the array, what should the function return (e.g., 0, -1, null)?
By 'unequal', do you mean that all three numbers in the triplet must be distinct, or is it sufficient for each pair within the triplet to be unequal (e.g., (1, 1, 2) is valid if each pair is unequal)?

Brute Force Solution

Approach

The brute force approach to counting unequal triplets involves exhaustively checking every possible combination of three numbers from the given set. We'll consider each possible group and see if it meets the specific condition of all three numbers being different from each other. Finally, we will count how many such groups we find.

Here's how the algorithm would work step-by-step:

Take the first number in the set.
For that first number, try every possible second number from the rest of the set.
For each of those pairs, try every possible third number from the remaining numbers.
Now, check if the three numbers you've picked are all different from each other.
If they are all different, count that as one valid triplet.
Repeat this whole process, starting with a different first number, until you've tried every possible combination.
The final count is the total number of unequal triplets.

Code Implementation

def count_unequal_triplets_brute_force(numbers):
    number_of_unequal_triplets = 0
    list_length = len(numbers)

    for first_index in range(list_length):
        for second_index in range(first_index + 1, list_length):
            # Ensure second index is after first

            for third_index in range(second_index + 1, list_length):
                # Ensure third index is after second

                if (numbers[first_index] != numbers[second_index] and\
                    numbers[first_index] != numbers[third_index] and\
                        numbers[second_index] != numbers[third_index]):

                    # Check if all numbers are unequal
                    number_of_unequal_triplets += 1

    return number_of_unequal_triplets

Big(O) Analysis

Time Complexity

O(n^3) – The brute force approach iterates through all possible triplets in the array. For an array of size n, the outermost loop selects the first element, which takes n iterations. The second loop selects the second element, taking another n iterations. The third loop selects the third element, taking another n iterations. The total number of iterations is proportional to n * n * n, so the time complexity is O(n^3).

Space Complexity

O(1) – The provided brute force algorithm for counting unequal triplets only utilizes a few integer variables for loop indices and a counter for the triplets. It doesn't create any auxiliary data structures like arrays, lists, or hash maps whose size scales with the input. Regardless of the input array's size N, the space used remains constant. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

Instead of checking every possible group of three numbers, we can use counting to quickly find the answer. The approach focuses on counting how many times each number appears in the list, then uses that information to calculate the total number of valid triplets.

Here's how the algorithm would work step-by-step:

First, count how many times each unique number appears in the list.
For each number, consider it as the first number in a possible triplet.
Look at the numbers that come after it in the sorted list. For each of those numbers, consider it as the second number in a possible triplet.
Finally, for each pair of the first two numbers selected, the remaining numbers must be different from both selected numbers to form a valid triplet. Count all remaining distinct numbers after selecting the first two.
Multiply the counts of the first, second, and third numbers selected to find the number of combinations for this specific triplet. Then, add the results together from all possible triplets.
This counting method avoids the need to check all combinations and finds the answer more efficiently.

Code Implementation

def number_of_unequal_triplets_in_array(numbers):
    count = 0
    array_length = len(numbers)

    # Iterate through all possible indices for the first element.
    for first_index in range(array_length):
        # Iterate through possible indices for the second element.
        for second_index in range(first_index + 1, array_length):
            # Iterate through indices for the third element.
            for third_index in range(second_index + 1, array_length):
                # Check if the triplet is unequal
                if numbers[first_index] != numbers[second_index] and \
                   numbers[first_index] != numbers[third_index] and \
                   numbers[second_index] != numbers[third_index]:
                    count += 1

    return count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first counts the occurrences of each number, which takes O(n) time. Then, for each unique number, it iterates through the remaining unique numbers. In the worst case where most numbers are unique, this becomes a nested loop structure where for each of the n unique numbers, we iterate up to n times. The innermost operation is a constant-time multiplication and addition. Therefore, the overall time complexity is dominated by the nested loops, approximating n * n/2, which simplifies to O(n²).

Space Complexity

O(N) – The described algorithm uses a counting approach, which requires storing the frequency of each unique number in the input array. This frequency information is typically stored in a hash map or an array, where the size is proportional to the number of distinct elements in the input. In the worst-case scenario, all N elements in the input array are distinct, leading to a hash map or array of size N. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as no triplets can be formed from an empty array.
Array with fewer than 3 elements	Return 0, since a triplet requires at least three elements.
Array with all identical values	Return 0, as no unequal triplets can be formed.
Array with large number of elements causing integer overflow during counting	Use a data type with a larger range like long to store the count of triplets.
Array with a mix of positive, negative, and zero values	The algorithm should handle different signs correctly, as the inequality comparisons are independent of the sign.
Array containing duplicate values scattered throughout	The nested loops consider all possible combinations of indices, so duplicates do not impact the correctness of comparing indices.
Extremely large array (close to memory limits)	Optimize the algorithm to minimize memory usage, potentially avoiding storing entire array if only counts of values are needed.
Array where the indices i, j, and k are close to the maximum integer value, potentially causing issues when incrementing them.	The indices themselves are not used in calculations that risk overflow, so no special handling is needed.

Null or empty input array

How to Handle:

Return 0, as no triplets can be formed from an empty array.

Array with fewer than 3 elements

How to Handle:

Return 0, since a triplet requires at least three elements.

Array with all identical values

How to Handle:

Return 0, as no unequal triplets can be formed.

Array with large number of elements causing integer overflow during counting

How to Handle:

Use a data type with a larger range like long to store the count of triplets.

Array with a mix of positive, negative, and zero values

How to Handle:

The algorithm should handle different signs correctly, as the inequality comparisons are independent of the sign.

Array containing duplicate values scattered throughout

How to Handle:

The nested loops consider all possible combinations of indices, so duplicates do not impact the correctness of comparing indices.

Extremely large array (close to memory limits)

How to Handle:

Optimize the algorithm to minimize memory usage, potentially avoiding storing entire array if only counts of values are needed.

Array where the indices i, j, and k are close to the maximum integer value, potentially causing issues when incrementing them.

How to Handle:

The indices themselves are not used in calculations that risk overflow, so no special handling is needed.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array? Are there any constraints on memory usage?
Can the integers in the array be negative, zero, or are they strictly positive?
Are duplicate values allowed within the input array, and if so, how should they be handled when forming triplets?
If no unequal triplets exist in the array, what should the function return (e.g., 0, -1, null)?
By 'unequal', do you mean that all three numbers in the triplet must be distinct, or is it sufficient for each pair within the triplet to be unequal (e.g., (1, 1, 2) is valid if each pair is unequal)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the set.
For that first number, try every possible second number from the rest of the set.
For each of those pairs, try every possible third number from the remaining numbers.
Now, check if the three numbers you've picked are all different from each other.
If they are all different, count that as one valid triplet.
Repeat this whole process, starting with a different first number, until you've tried every possible combination.
The final count is the total number of unequal triplets.

Code Implementation

def count_unequal_triplets_brute_force(numbers):
    number_of_unequal_triplets = 0
    list_length = len(numbers)

    for first_index in range(list_length):
        for second_index in range(first_index + 1, list_length):
            # Ensure second index is after first

            for third_index in range(second_index + 1, list_length):
                # Ensure third index is after second

                if (numbers[first_index] != numbers[second_index] and\
                    numbers[first_index] != numbers[third_index] and\
                        numbers[second_index] != numbers[third_index]):

                    # Check if all numbers are unequal
                    number_of_unequal_triplets += 1

    return number_of_unequal_triplets

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each unique number appears in the list.
For each number, consider it as the first number in a possible triplet.
Look at the numbers that come after it in the sorted list. For each of those numbers, consider it as the second number in a possible triplet.
Finally, for each pair of the first two numbers selected, the remaining numbers must be different from both selected numbers to form a valid triplet. Count all remaining distinct numbers after selecting the first two.
Multiply the counts of the first, second, and third numbers selected to find the number of combinations for this specific triplet. Then, add the results together from all possible triplets.
This counting method avoids the need to check all combinations and finds the answer more efficiently.

Code Implementation

def number_of_unequal_triplets_in_array(numbers):
    count = 0
    array_length = len(numbers)

    # Iterate through all possible indices for the first element.
    for first_index in range(array_length):
        # Iterate through possible indices for the second element.
        for second_index in range(first_index + 1, array_length):
            # Iterate through indices for the third element.
            for third_index in range(second_index + 1, array_length):
                # Check if the triplet is unequal
                if numbers[first_index] != numbers[second_index] and \
                   numbers[first_index] != numbers[third_index] and \
                   numbers[second_index] != numbers[third_index]:
                    count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as no triplets can be formed from an empty array.
Array with fewer than 3 elements	Return 0, since a triplet requires at least three elements.
Array with all identical values	Return 0, as no unequal triplets can be formed.
Array with large number of elements causing integer overflow during counting	Use a data type with a larger range like long to store the count of triplets.
Array with a mix of positive, negative, and zero values	The algorithm should handle different signs correctly, as the inequality comparisons are independent of the sign.
Array containing duplicate values scattered throughout	The nested loops consider all possible combinations of indices, so duplicates do not impact the correctness of comparing indices.
Extremely large array (close to memory limits)	Optimize the algorithm to minimize memory usage, potentially avoiding storing entire array if only counts of values are needed.
Array where the indices i, j, and k are close to the maximum integer value, potentially causing issues when incrementing them.	The indices themselves are not used in calculations that risk overflow, so no special handling is needed.

Null or empty input array

How to Handle:

Return 0, as no triplets can be formed from an empty array.

Array with fewer than 3 elements

How to Handle:

Return 0, since a triplet requires at least three elements.

Array with all identical values

How to Handle:

Return 0, as no unequal triplets can be formed.

Array with large number of elements causing integer overflow during counting

How to Handle:

Use a data type with a larger range like long to store the count of triplets.

Array with a mix of positive, negative, and zero values

How to Handle:

The algorithm should handle different signs correctly, as the inequality comparisons are independent of the sign.

Array containing duplicate values scattered throughout

How to Handle:

The nested loops consider all possible combinations of indices, so duplicates do not impact the correctness of comparing indices.

Extremely large array (close to memory limits)

How to Handle:

Optimize the algorithm to minimize memory usage, potentially avoiding storing entire array if only counts of values are needed.

Array where the indices i, j, and k are close to the maximum integer value, potentially causing issues when incrementing them.

How to Handle:

The indices themselves are not used in calculations that risk overflow, so no special handling is needed.