Welcome to Subscribe On Youtube
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] <= 10^{5}
 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; }