1395. Count Number of Teams

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.

Approach 01:

#include <vector>

using namespace std;

class Solution {
public:
    int numTeams(vector<int>& ratings) {
        int totalTeams = 0;

        // Iterate through each soldier, considering them as the middle soldier in a team
        for (int middle = 1; middle < ratings.size() - 1; ++middle) {
            // Calculate the number of soldiers on the left with less/greater ratings than the middle soldier
            int leftLessCount = 0;
            int leftGreaterCount = 0;
            for (int left = 0; left < middle; ++left) {
                if (ratings[left] < ratings[middle]) {
                    ++leftLessCount;
                } else if (ratings[left] > ratings[middle]) {
                    ++leftGreaterCount;
                }
            }

            // Calculate the number of soldiers on the right with less/greater ratings than the middle soldier
            int rightLessCount = 0;
            int rightGreaterCount = 0;
            for (int right = middle + 1; right < ratings.size(); ++right) {
                if (ratings[right] < ratings[middle]) {
                    ++rightLessCount;
                } else if (ratings[right] > ratings[middle]) {
                    ++rightGreaterCount;
                }
            }

            // Calculate the number of valid teams using the current middle soldier
            totalTeams += leftLessCount * rightGreaterCount + leftGreaterCount * rightLessCount;
        }

        return totalTeams;
    }
};

from typing import List

class Solution:
    def numTeams(self, ratings: List[int]) -> int:
        totalTeams = 0

        # Iterate through each soldier, considering them as the middle soldier in a team
        for middle in range(1, len(ratings) - 1):
            # Calculate the number of soldiers on the left with less/greater ratings than the middle soldier
            leftLessCount = 0
            leftGreaterCount = 0
            for left in range(middle):
                if ratings[left] < ratings[middle]:
                    leftLessCount += 1
                elif ratings[left] > ratings[middle]:
                    leftGreaterCount += 1

            # Calculate the number of soldiers on the right with less/greater ratings than the middle soldier
            rightLessCount = 0
            rightGreaterCount = 0
            for right in range(middle + 1, len(ratings)):
                if ratings[right] < ratings[middle]:
                    rightLessCount += 1
                elif ratings[right] > ratings[middle]:
                    rightGreaterCount += 1

            # Calculate the number of valid teams using the current middle soldier
            totalTeams += leftLessCount * rightGreaterCount + leftGreaterCount * rightLessCount

        return totalTeams

Time Complexity

• Initialization:

  Initializing totalTeams takes \( O(1) \) time.

• Outer Loop:

  The outer loop iterates through each soldier considering them as the middle soldier in a team, which takes \( O(n) \) time, where \( n \) is the number of soldiers.

• Inner Loops:

  For each middle soldier, there are two inner loops:

  • The first inner loop iterates over the left part of the array, taking \( O(n) \) time in the worst case.
  • The second inner loop iterates over the right part of the array, also taking \( O(n) \) time in the worst case.

  Therefore, each iteration of the outer loop takes \( O(n + n) = O(n) \) time.

• Overall Time Complexity:

  Since the outer loop runs \( n \) times and each iteration takes \( O(n) \) time, the overall time complexity is \( O(n^2) \).

Space Complexity

• Space for Variables:

  The space used by variables totalTeams, leftLessCount, leftGreaterCount, rightLessCount, and rightGreaterCount is \( O(1) \).

• Input Array:

  The input array is not modified, so no additional space is required for the input data.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).