Leetcode 1395. Count Number of Teams

1395. Count Number of Teams

Medium

Arrays

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

• Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
• A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

 

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

 

Constraints:

• n == rating.length
• 3 <= n <= 1000
• 1 <= rating[i] <= 105
• All the integers in rating are unique.

Here is the solution to the problem, including multiple approaches explained in detail:

---

Approach 1: Brute Force

The simplest approach is to use three nested loops to iterate over all possible triplets (i, j, k) and check the conditions (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]).

Code:

public int NumTeamsBruteForce(int[] rating)
{
    int n = rating.Length;
    int count = 0;

    for (int i = 0; i < n - 2; i++)
    {
        for (int j = i + 1; j < n - 1; j++)
        {
            for (int k = j + 1; k < n; k++)
            {
                if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
                    (rating[i] > rating[j] && rating[j] > rating[k]))
                {
                    count++;
                }
            }
        }
    }

    return count;
}

Explanation:

1. Three nested loops iterate through all combinations of indices (i, j, k).
2. Check the two conditions for a valid team.
3. If either condition is met, increment the count.
4. Time Complexity: $O(n^3)$, which is inefficient for larger arrays.

---

Approach 2: Optimized with Pre-computation

Instead of checking conditions for all triplets, we calculate the number of smaller and larger elements for each element to reduce redundant comparisons.

Code:

public int NumTeamsOptimized(int[] rating)
{
    int n = rating.Length;
    int count = 0;

    for (int j = 0; j < n; j++)
    {
        int leftSmaller = 0, leftLarger = 0, rightSmaller = 0, rightLarger = 0;

        // Count elements smaller and larger on the left of j
        for (int i = 0; i < j; i++)
        {
            if (rating[i] < rating[j]) leftSmaller++;
            else if (rating[i] > rating[j]) leftLarger++;
        }

        // Count elements smaller and larger on the right of j
        for (int k = j + 1; k < n; k++)
        {
            if (rating[k] < rating[j]) rightSmaller++;
            else if (rating[k] > rating[j]) rightLarger++;
        }

        // Teams can be formed in two ways
        count += leftSmaller * rightLarger; // Increasing triplet
        count += leftLarger * rightSmaller; // Decreasing triplet
    }

    return count;
}

Explanation:

1. For each soldier j, count the number of soldiers smaller and larger to its left and right.
2. Use these counts to calculate the number of increasing and decreasing triplets that include soldier j.
3. Time Complexity: $O(n^2)$, as we only use two loops.
4. Space Complexity: $O(1)$, no extra data structures are used.

---

Approach 3: Binary Indexed Tree (BIT) or Fenwick Tree

This approach uses a Fenwick Tree for efficient prefix sum calculations to find the number of smaller and larger elements dynamically.

Code:

public int NumTeamsBIT(int[] rating)
{
    int n = rating.Length;
    int maxValue = 100000; // Given constraint on rating[i]
    int[] smallerLeft = new int[n];
    int[] largerRight = new int[n];

    int[] fenwick = new int[maxValue + 1];

    // Count smaller elements on the left
    for (int i = 0; i < n; i++)
    {
        smallerLeft[i] = Query(fenwick, rating[i] - 1);
        Update(fenwick, rating[i], 1);
    }

    Array.Clear(fenwick, 0, fenwick.Length);

    // Count larger elements on the right
    for (int i = n - 1; i >= 0; i--)
    {
        largerRight[i] = Query(fenwick, maxValue) - Query(fenwick, rating[i]);
        Update(fenwick, rating[i], 1);
    }

    int count = 0;
    for (int i = 0; i < n; i++)
    {
        count += smallerLeft[i] * largerRight[i];
        count += (i - smallerLeft[i]) * (n - i - 1 - largerRight[i]);
    }

    return count;
}

// Fenwick Tree Helper Methods
private void Update(int[] fenwick, int index, int value)
{
    while (index < fenwick.Length)
    {
        fenwick[index] += value;
        index += index & -index;
    }
}

private int Query(int[] fenwick, int index)
{
    int sum = 0;
    while (index > 0)
    {
        sum += fenwick[index];
        index -= index & -index;
    }
    return sum;
}

Explanation:

1. Use a Fenwick Tree to efficiently calculate prefix sums.
2. For each element, calculate how many elements are smaller to its left and larger to its right.
3. Combine these counts to calculate the total number of valid teams.
4. Time Complexity: $O(n \log \text{maxValue})$, where maxValue is the maximum possible rating.
5. Space Complexity: $O(\text{maxValue})$.

---

Comparison of Approaches:

Approach	Time Complexity	Space Complexity	Suitable For
Brute Force	$O(n^3)$	$O(1)$	Small inputs
Optimized	$O(n^2)$	$O(1)$	Moderate inputs
Fenwick Tree (BIT)	$O(n \log n)$	$O(\text{maxValue})$	Large inputs with constraints

Let me know if you have further questions or need additional explanations!