Count Number of Teams

Leetcode Problem:

• Count Number of Teams

Summary

• Count the number of teams that can be formed from a list of unique ratings.

Approach

• The solution uses a two-pointer technique to count the number of teams that can be formed
• It iterates over the list of ratings, and for each rating, it counts the number of ratings to its left and right that are less than and greater than the current rating
• The number of teams that can be formed with the current rating is then calculated by multiplying the number of ratings to its left and right that are less than and greater than the current rating, respectively
• The total number of teams is then calculated by summing up the number of teams that can be formed for each rating.

Complexity

• O(N^2) where N is the number of ratings.

Explain

• The solution iterates over the list of ratings and for each rating, it counts the number of ratings to its left and right that are less than and greater than the current rating
• The number of teams that can be formed with the current rating is then calculated by multiplying the number of ratings to its left and right that are less than and greater than the current rating, respectively
• The total number of teams is then calculated by summing up the number of teams that can be formed for each rating
• This approach ensures that each rating is counted multiple times, but it is necessary to count the number of teams that can be formed for each rating
• The time complexity of the solution is O(N^2) because the solution iterates over the list of ratings and for each rating, it counts the number of ratings to its left and right that are less than and greater than the current rating.

Solution Code:

class Solution {
public:
    int ans = 0;
    int numTeams(vector& rating) {
        int N = rating.size();
        for(int i = 1; i < N - 1; i++){
            int leftCnt1 = 0;
            int leftCnt2 = 0;
            int idx = i - 1;
            while(idx >= 0){
                if(rating[idx] < rating[i]){
                    leftCnt1++;
                }
                if(rating[idx] > rating[i]){
                    leftCnt2++;
                }
                idx--;
            }
            int rightCnt1 = 0;
            int rightCnt2 = 0;
            idx = i + 1;
            while(idx < N){
                if(rating[i] < rating[idx]){
                    rightCnt1++;
                }
                if(rating[i] > rating[idx]){
                    rightCnt2++;
                }
                idx++;
            }
            ans += leftCnt1 * rightCnt1;
            ans += leftCnt2 * rightCnt2;
        }
        return ans;
    }
};