Count Number Of Teams - Leetcode Solution

Count Number Of Teams is a problem on LeetCode that requires you to find the number of ways you can create a team of soldiers. The problem is the following:

You have n soldiers numbered from 1 to n. Each soldier has a unique rating r[i]. You want to form a team of 3 soldiers among them under the following rules:

1. Choose 3 soldiers with index (i, j, k) with rating (r[i], r[j], r[k]).
2. A team is valid if: (r[i] < r[j] < r[k]) or (r[i] > r[j] > r[k]) where (0 <= i < j < k < n).
3. Return the number of teams you can form given the conditions.

Here is a detailed solution in Python:

def numTeams(ratings):
    n = len(ratings)
    res = 0
    
    for i in range(n):
        left_small, right_large = 0, 0
        left_large, right_small = 0, 0
        
        # Finding the number of soldiers with smaller and greater ratings than soldier i on its left and right sides
        for j in range(i):
            if ratings[i] > ratings[j]:
                left_small += 1
            else:
                left_large += 1

        for k in range(i+1, n):
            if ratings[i] < ratings[k]:
                right_large += 1
            else:
                right_small += 1
        
        # Adding the number of valid teams we can form using soldier i as a middle soldier
        res += left_small * right_large + left_large * right_small
    
    return res

Explanation:

We start by initializing a variable res to 0 which will keep track of the number of valid teams we can form.

We then iterate over each soldier i from 0 to n-1 and for each soldier, we find the number of soldiers on its left and right sides with smaller and greater ratings, respectively. We do this by iterating over the ratings array twice.

Once we have the count of soldiers with greater/smaller ratings on both sides of i, we can use this to compute the number of valid teams we can form with i as a middle soldier.

To do this, we use the formula left_small * right_large + left_large * right_small. This formula calculates the number of valid teams where i is in the middle using the counts we computed earlier. The left_small * right_large term gives the number of valid teams where i has a smaller rating than its left and larger rating than its right and the left_large * right_small term gives the number of valid teams where i has a larger rating than its left and smaller rating than its right.

Finally, we return the value of res which gives us the total number of valid teams we can form.

1