# 1395. Count Number of Teams

## Description

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.

## Solutions

Solution 1: Enumerate Middle Element

We can enumerate each element $rating[i]$ in the array $rating$ as the middle element, then count the number of elements $l$ that are smaller than it on the left, and the number of elements $r$ that are larger than it on the right. The number of combat units with this element as the middle element is $l \times r + (i - l) \times (n - i - 1 - r)$. We can add this to the answer.

The time complexity is $O(n^2)$, and the space complexity is $O(1)$. Where $n$ is the length of the array $rating$.

Solution 2: Binary Indexed Tree

We can use two binary indexed trees to maintain the number of elements $l$ that are smaller than each element on the left in the array $rating$, and the number of elements $r$ that are larger than it on the right. Then count the number of combat units with this element as the middle element as $l \times r + (i - l) \times (n - i - 1 - r)$, and add this to the answer.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the length of the array $rating$.

• class Solution {
public int numTeams(int[] rating) {
int n = rating.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
int l = 0, r = 0;
for (int j = 0; j < i; ++j) {
if (rating[j] < rating[i]) {
++l;
}
}
for (int j = i + 1; j < n; ++j) {
if (rating[j] > rating[i]) {
++r;
}
}
ans += l * r;
ans += (i - l) * (n - i - 1 - r);
}
return ans;
}
}

• class Solution {
public:
int numTeams(vector<int>& rating) {
int n = rating.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
int l = 0, r = 0;
for (int j = 0; j < i; ++j) {
if (rating[j] < rating[i]) {
++l;
}
}
for (int j = i + 1; j < n; ++j) {
if (rating[j] > rating[i]) {
++r;
}
}
ans += l * r;
ans += (i - l) * (n - i - 1 - r);
}
return ans;
}
};

• class Solution:
def numTeams(self, rating: List[int]) -> int:
ans, n = 0, len(rating)
for i, b in enumerate(rating):
l = sum(a < b for a in rating[:i])
r = sum(c > b for c in rating[i + 1 :])
ans += l * r
ans += (i - l) * (n - i - 1 - r)
return ans


• func numTeams(rating []int) (ans int) {
n := len(rating)
for i, b := range rating {
l, r := 0, 0
for _, a := range rating[:i] {
if a < b {
l++
}
}
for _, c := range rating[i+1:] {
if c < b {
r++
}
}
ans += l * r
ans += (i - l) * (n - i - 1 - r)
}
return
}

• function numTeams(rating: number[]): number {
let ans = 0;
const n = rating.length;
for (let i = 0; i < n; ++i) {
let l = 0;
let r = 0;
for (let j = 0; j < i; ++j) {
if (rating[j] < rating[i]) {
++l;
}
}
for (let j = i + 1; j < n; ++j) {
if (rating[j] > rating[i]) {
++r;
}
}
ans += l * r;
ans += (i - l) * (n - i - 1 - r);
}
return ans;
}