2475. Number of Unequal Triplets in Array

EasyArrayHash Table
Leetcode Link

Problem Description

You are provided with an array of positive integers called nums. Each element of the array has a 0-based index. The task is to find out how many groups of three indices (i, j, k) exist such that the following conditions are met:

  1. The indices are in strictly increasing order, i.e., i < j < k.
  2. The values of nums at these indices are pairwise distinct. This means that nums[i], nums[j], and nums[k] should all be different from each other.

In other words, for a triplet (i, j, k) to be counted, it must consist of three unique numbers from the nums array, each coming from a unique position in the array, where i, j, and k represent the positions (indices) of these numbers.

The goal is to return the count of all such triplets.

Intuition

To solve this problem, we need to find a way to calculate the number of distinct triplets without having to manually check each possible combination, which would be inefficient especially for large arrays.

We can use the following approach:

  1. Count the frequency of each number in the array using a data structure like a dictionary (Counter in Python).
  2. Iterate through each unique number's frequency, calculating how many distinct triplets can be formed with it.

The intuition stems from the fact that if we know how many times a particular number occurs, and how many numbers are before and after it in the array (that haven't been used in a triplet yet), we can calculate all the valid triplets it can form.

Here are the steps taken in the solution code:

  • Use Counter to get the frequency of each distinct number in nums.
  • Initialize two counters, ans and a. ans will hold the final count of triplets, and a will keep track of the count of numbers processed so far.
  • Loop through the frequency count of each distinct number:
    • Let b represent the frequency of the current number.
    • Calculate c as the number of remaining elements that come after the current number, which is n - a - b (where n is the total length of nums).
    • The number of triplets we can form with the current number as the middle element is a * b * c. This product comes from selecting one of the numbers before the current one (a choices), the current number itself (b choices), and one of the numbers after (c choices).
    • Add this triplet count to the ans.
    • Update a to include the current number as well by adding b to it.
  • The final answer is contained in ans, so we return it.

By using this method, we efficiently calculate the number of distinct triplets without the need to individually consider each possible combination of three numbers.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement recursion?

Solution Approach

The solution approach is based on the concept of counting and combinatorics. To implement the solution, the following components are used:

  • Data Structures:

    • We use the Counter class from Python's collections module to efficiently count the frequency of each element in the nums array.
    • A dictionary-like container maps unique elements to their respective frequencies.

  • Variables:

    • cnt: A Counter object that holds the frequency of each unique element in nums.
    • n: The total number of elements in nums.
    • ans: An accumulator to sum the number of valid triplets found.
    • a: Keeps track of the number of elements processed so far (left side of the current element).
    • b: The frequency of the current element being considered as the middle element of a triplet.
    • c: Represents the number of elements that are available to be picked after the current element.

  • Algorithm:

    1. Count the frequency of each unique number using cnt = Counter(nums).
    2. Initialize a variable ans to accumulate the total number of valid triplets and a variable a to keep track of the count of numbers already processed.
    3. Iterate over each count b in the values of cnt (since keys represent the unique numbers and values their respective counts):
      • Calculate the number of available elements after the current element (which could potentially be the third element of the triplet) as c = n - a - b.
      • Calculate the number of triplets possible with the current number as the middle element as a * b * c and add this to ans.
      • Update a to include the element just processed by adding b to it.
    4. After the loop ends, ans holds the total number of valid triplets, which is returned as the final answer.

Each step of the algorithm is designed to avoid checking each triplet individually by leveraging the frequency counts and positions of numbers to calculate the number of potential triplets directly. This leads to a more efficient implementation that can handle large arrays without incurring a performance penalty typical of brute-force solutions.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

Example Walkthrough

Let's consider an example nums array to illustrate the solution approach:

1nums = [1, 1, 2, 2, 3]

From the problem statement, we want to count distinct triplets (i, j, k) such that nums[i], nums[j], and nums[k] are all unique.

  1. First, we use Counter to get the frequency of each unique number in nums.
1from collections import Counter
2cnt = Counter(nums)  # cnt will be Counter({1: 2, 2: 2, 3: 1})

  1. We set n to the total number of elements in nums, which is 5.

  2. Initialize the variables ans for the total number of valid triplets and a for counting processed numbers.

1ans = 0
2a = 0

  1. Now, we iterate over each count b in the values of cnt. The dictionary cnt has elements along with their frequencies: {1: 2, 2: 2, 3: 1}.

    • First iteration (for number 1):
      • b for number 1 is 2.
      • c = n - a - b which is 5 - 0 - 2 = 3. There are three elements that can come after the first 1 to form a triplet.
      • Triplet count for 1 is a * b * c = 0 * 2 * 3 = 0 (since a is 0, no triplets can be formed with 1 as the middle element yet).
      • Update a = a + b to 2 (since we've now processed two occurrences of 1).
    • Second iteration (for number 2):
      • b for number 2 is 2.
      • c = n - a - b which is 5 - 2 - 2 = 1. There is one element that can come after 2 to form a triplet.
      • Triplet count for 2 is a * b * c = 2 * 2 * 1 = 4. We can form 4 triplets with 2 as the middle element.
      • Update ans by adding the triplet count, ans = ans + 4 to 4.
      • Update a = a + b to 4 (as we've now processed two occurrences of 2).
    • Third iteration (for number 3):
      • b for number 3 is 1.
      • c = n - a - b which is 5 - 4 - 1 = 0. There are no elements left to form triplets with 3 as the middle element.
      • Triplet count for 3 is a * b * c = 4 * 1 * 0 = 0. No additional triplets can be formed.
      • ans remains 4.

  2. After the iteration ends, ans holds the total number of valid triplets. For this example, there are 4 valid triplets, and thus we return 4.

To conclude, using this example with nums = [1, 1, 2, 2, 3], the algorithm efficiently found the total number of 4 distinct triplets without having to check each possible combination of three numbers.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def unequalTriplets(self, nums: List[int]) -> int:
5        # Count the frequency of each number in nums
6        number_counts = Counter(nums)
7        total_numbers = len(nums)
8      
9        # Initialize the answer and the count for the first number in the triplet
10        answer = count_first_number = 0
11      
12        # Iterating through the counts of each unique number
13        for count_second_number in number_counts.values():
14            # Count of the third number in the triplet is total_numbers
15            # minus the count_first_number and count_second_number
16            count_third_number = total_numbers - count_first_number - count_second_number
17          
18            # Calculate the number of triplets where the first, second, and third numbers
19            # are all different
20            answer += count_first_number * count_second_number * count_third_number
21          
22            # Increment count_first_number for the next iteration of the loop
23            count_first_number += count_second_number
24      
25        # Return the total number of unequal triplets
26        return answer
27
1class Solution {
2    public int unequalTriplets(int[] nums) {
3        // Create a map to store the frequency of each number in the array
4        Map<Integer, Integer> frequencyMap = new HashMap<>();
5        for (int num : nums) {
6            // If the number is already in the map, increment its frequency,
7            // otherwise insert it with frequency 1
8            frequencyMap.merge(num, 1, Integer::sum);
9        }
10
11        // Initialize the answer variable to store the count of unequal triplets
12        int answer = 0;
13
14        // Variable 'prefixCount' is used to keep track of the count of numbers processed so far
15        int prefixCount = 0;
16
17        // 'n' is the total number of elements in the input array
18        int n = nums.length;
19
20        // Iterate through the frequency map
21        for (int frequency : frequencyMap.values()) {
22            // Calculate the count of numbers remaining after excluding the current number
23            int suffixCount = n - prefixCount - frequency;
24
25            // Update the answer by adding the number of unequal triplets that can be formed
26            answer += prefixCount * frequency * suffixCount;
27
28            // Update the prefix count by adding the frequency of the current number
29            prefixCount += frequency;
30        }
31
32        // Return the final count of unequal triplets
33        return answer;
34    }
35}
36
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    // This function counts the number of unequal triplets within the input vector.
8    int unequalTriplets(vector<int>& nums) {
9        // Create a hash table to keep track of the count of each number in the vector.
10        unordered_map<int, int> numCounts;
11        // Increment the count for each value in the nums vector.
12        for (int value : nums) {
13            ++numCounts[value];
14        }
15
16        int result = 0;    // Variable to store the result.
17        int accumulated = 0; // Accumulated counts of previous numbers.
18
19        // Calculate the number of unequal triplets.
20        for (auto& [value, count] : numCounts) {
21            int remaining = nums.size() - accumulated - count; // Count of numbers that are not equal to current number.
22            result += accumulated * count * remaining; // Multiply by count to form unequal triplets.
23            accumulated += count; // Update accumulated with count of the current number.
24        }
25
26        // Return the total number of unequal triplets.
27        return result;
28    }
29};
30
1function unequalTriplets(nums: number[]): number {
2    // Find the length of the nums array
3    const lengthOfNums = nums.length;
4    // Initialize a map to keep count of each number's occurrences
5    const countMap = new Map<number, number>();
6  
7    // Count the occurrences of each number in the nums array
8    for (const num of nums) {
9        countMap.set(num, (countMap.get(num) ?? 0) + 1);
10    }
11  
12    // Initialize variable to hold the result
13    let result = 0;
14    // 'accumulated' will keep track of the accumulated counts for each processed number
15    let accumulated = 0;
16  
17    // Iterate over the map to calculate the answer using the formula
18    for (const currentCount of countMap.values()) {
19        // Calculate the count for the third element in the triplet
20        const remaining = lengthOfNums - accumulated - currentCount;
21        // Calculate the number of unequal triplets for the current iteration
22        result += accumulated * currentCount * remaining;
23        // Update the accumulated count
24        accumulated += currentCount;
25    }
26  
27    // Return the total number of unequal triplets
28    return result;
29}
30
Not Sure What to Study? Take the 2-min Quiz：

Which of these pictures shows the visit order of a depth-first search?

Time and Space Complexity

Time Complexity

The time complexity of the code is primarily determined by the number of operations within the for loop which iterates over the values of the Counter object cnt. The Counter object itself is created by iterating over the nums list once, which takes O(n) time where n is the number of elements in nums.

Inside the for loop, each operation is constant time, so the overall time complexity of the for loop is O(k), where k is the number of unique elements in nums. Since k can vary from 1 to n, in the worst case where all elements are unique, k is equal to n.

Therefore, the total time complexity is O(n) + O(k) = O(n) as the first iteration to create Counter and the second iteration over unique values can be bounded by n.

Space Complexity

The space complexity is affected by the storage used for the Counter object cnt which stores the frequency of each unique element in nums. In the worst case, if all elements of nums are unique, the Counter would take O(n) space where n is the number of elements in nums.

Thus, the overall space complexity of the code is O(n).

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

Fast Track Your Learning with Our Quick Skills Quiz:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫