Problem Description

The "Count Number of Teams" problem asks you to determine how many teams of three soldiers can be formed from a given array of soldier ratings, such that the ratings of the three soldiers are either strictly increasing or strictly decreasing. Each team must consist of three distinct soldiers with indices i, j, and k such that 0 ≤ i < j < k < n, where n is the length of the rating array.

• You cannot reuse any soldier in a team.
• Each team must have exactly three members.
• The order of selection matters (i.e., indices must be in increasing order).
• The team is valid if either rating[i] < rating[j] < rating[k] (strictly increasing) or rating[i] > rating[j] > rating[k] (strictly decreasing).

Thought Process

The first idea that comes to mind is to check every possible combination of three different soldiers (i.e., every possible triplet of indices (i, j, k) with i < j < k), and count how many of these triplets form a valid team. This is a brute-force approach, but as the input size grows, it becomes inefficient.

To optimize, we realize that for each possible "middle" soldier (at index j), we can count how many soldiers before j have a lower (or higher) rating, and how many soldiers after j have a higher (or lower) rating. By multiplying these counts, we can efficiently determine the number of valid teams where j is the middle member.

This shift in perspective—from checking all triplets to counting possible left and right partners for each middle member—allows us to reduce the number of operations significantly.

Solution Approach

We'll use an efficient approach that iterates through each soldier as the potential "middle" member of a team. For each soldier at index j:

1. Count soldiers to the left of j:
   • less_left: Number of soldiers before j with a rating less than rating[j].
   • greater_left: Number of soldiers before j with a rating greater than rating[j].
2. Count soldiers to the right of j:
   • less_right: Number of soldiers after j with a rating less than rating[j].
   • greater_right: Number of soldiers after j with a rating greater than rating[j].
3. Calculate:
   • The number of increasing teams with j in the middle is less_left * greater_right.
   • The number of decreasing teams with j in the middle is greater_left * less_right.
4. Sum up: For each j, sum these products to get the total number of valid teams.

This approach is much faster than brute-force, as it avoids checking all possible triplets directly.

Example Walkthrough

Let's use the input rating = [2, 5, 3, 4, 1].

• For j = 1 (rating[1] = 5):
  • less_left: rating[0] = 2 is less than 5 → 1
  • greater_left: 0
  • less_right: rating[2]=3, rating[3]=4, rating[4]=1 are all less than 5 → 3
  • greater_right: 0
  • Increasing teams: 1 * 0 = 0
  • Decreasing teams: 0 * 3 = 0
• For j = 2 (rating[2] = 3):
  • less_left: rating[0]=2 is less than 3 → 1
  • greater_left: rating[1]=5 is greater than 3 → 1
  • less_right: rating[4]=1 is less than 3 → 1
  • greater_right: rating[3]=4 is greater than 3 → 1
  • Increasing teams: 1 * 1 = 1
  • Decreasing teams: 1 * 1 = 1
• For j = 3 (rating[3] = 4):
  • less_left: rating[0]=2, rating[2]=3 are less than 4 → 2
  • greater_left: rating[1]=5 is greater than 4 → 1
  • less_right: rating[4]=1 is less than 4 → 1
  • greater_right: 0
  • Increasing teams: 2 * 0 = 0
  • Decreasing teams: 1 * 1 = 1
• Total valid teams: 1 (inc) + 1 (dec) + 1 (dec) = 3

Time and Space Complexity

• Brute-force approach:
  • Check every triplet: O(n³) time, where n is the number of soldiers.
  • Space: O(1) extra space.
• Optimized approach (described above):
  • For each soldier (as middle), count left and right possibilities: O(n²) time.
  • Space: O(1) extra space (not counting input).
• Why: For each of the n soldiers, we scan up to n elements on each side, resulting in O(n²) total operations.

Summary

The key insight for solving the "Count Number of Teams" problem efficiently is to treat each index as the potential middle of a team and count possible left and right partners, rather than checking all possible triplets. This reduces the time complexity from O(n³) to O(n²). The approach is both intuitive and efficient, making it well-suited for the problem's constraints.

Code Implementation

class Solution:
    def numTeams(self, rating):
        n = len(rating)
        result = 0
        for j in range(n):
            less_left = greater_left = 0
            less_right = greater_right = 0
            for i in range(j):
                if rating[i] < rating[j]:
                    less_left += 1
                elif rating[i] > rating[j]:
                    greater_left += 1
            for k in range(j+1, n):
                if rating[k] > rating[j]:
                    greater_right += 1
                elif rating[k] < rating[j]:
                    less_right += 1
            result += less_left * greater_right + greater_left * less_right
        return result
      

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int n = rating.size();
        int result = 0;
        for (int j = 0; j < n; ++j) {
            int less_left = 0, greater_left = 0, less_right = 0, greater_right = 0;
            for (int i = 0; i < j; ++i) {
                if (rating[i] < rating[j]) less_left++;
                else if (rating[i] > rating[j]) greater_left++;
            }
            for (int k = j+1; k < n; ++k) {
                if (rating[k] > rating[j]) greater_right++;
                else if (rating[k] < rating[j]) less_right++;
            }
            result += less_left * greater_right + greater_left * less_right;
        }
        return result;
    }
};
      

class Solution {
    public int numTeams(int[] rating) {
        int n = rating.length;
        int result = 0;
        for (int j = 0; j < n; ++j) {
            int lessLeft = 0, greaterLeft = 0, lessRight = 0, greaterRight = 0;
            for (int i = 0; i < j; ++i) {
                if (rating[i] < rating[j]) lessLeft++;
                else if (rating[i] > rating[j]) greaterLeft++;
            }
            for (int k = j + 1; k < n; ++k) {
                if (rating[k] > rating[j]) greaterRight++;
                else if (rating[k] < rating[j]) lessRight++;
            }
            result += lessLeft * greaterRight + greaterLeft * lessRight;
        }
        return result;
    }
}
      

var numTeams = function(rating) {
    let n = rating.length;
    let result = 0;
    for (let j = 0; j < n; ++j) {
        let lessLeft = 0, greaterLeft = 0, lessRight = 0, greaterRight = 0;
        for (let i = 0; i < j; ++i) {
            if (rating[i] < rating[j]) lessLeft++;
            else if (rating[i] > rating[j]) greaterLeft++;
        }
        for (let k = j + 1; k < n; ++k) {
            if (rating[k] > rating[j]) greaterRight++;
            else if (rating[k] < rating[j]) lessRight++;
        }
        result += lessLeft * greaterRight + greaterLeft * lessRight;
    }
    return result;
};