## Problem

**Problem ID**: 1511

**Title**: Count Number of Teams

**Difficulty**: Medium

**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:3Explanation: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:0Explanation: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**.

## Thoughts

As usual, I didn’t take a step back to think about the most optimal solution before attempting to solve this problem. The initial approach I took was the usual DP counting problem where the number of ways to form a team of 2 is add the number of ways soldier `i`

can join a team of 1 and the number of ways to form a team of 3 is to add the number of ways soldier `i`

can join a team of 2.

Initial solution (O(N^2)):

```
class Solution {
public:
int helper(const vector<int>& rating) {
const auto n = rating.size();
vector<int> dp(n,1);
for (size_t soldier = 1; soldier < 3; soldier++) {
vector<int> next_dp(n, 0);
for (size_t j = 0; j < n; j++) {
for (size_t i = 0; i < j; i++) {
if (rating[i] >= rating[j]) continue;
next_dp[j] += dp[i];
}
}
dp = move(next_dp);
}
int ret = 0;
for (const auto count : dp) {
ret += count;
}
return ret;
}
int numTeams(vector<int>& rating) {
int forward = helper(rating);
reverse(rating.begin(), rating.end());
int backward = helper(rating);
return forward + backward;
}
};
```

## Solution

**General Idea**

*Intuition*: Treat each solider as the middle `j`

solider and find the number of possible of `i`

(left) and number of possible `k`

(right).

To find the number of possible `i`

and `k`

:

- Two multiset (sorted)
- One multiset represents the soldiers to the left of
`j`

- One represents the soldiers to the right of
`j`

.

- One multiset represents the soldiers to the left of
- Finding the number of possible
`i`

is the number of elements in the left multiset that are strictly less than`rating[j]`

- This can be easily achieved by using
`lower_bound`

(the first element that`>= rating[j]`

) and moving it back by`1`

- Use
`std::distance`

to find the distance between the start and the new iterator

- This can be easily achieved by using
- Finding the number of possible
`j`

is the number of elements in the right multiset that are strictly greater than`rating[j]`

- This can be easily achieved by using
`upper_bound`

(the first element that`> rating[j]`

) - Use
`std::distance`

to find the distance between the new iterator and the end

- This can be easily achieved by using
- Complexity: O(log(N))

Multiplying the number of possible `i`

and `k`

will give the total groups with solider `j`

in the middle.

### Implementation

```
class Solution {
public:
int solve(const vector<int>& ratings) {
const auto n = ratings.size();
multiset<int> left;
multiset<int> right;
for (const auto rating : ratings) {
right.insert(rating);
}
int ret = 0;
for (size_t i = 0; i < n; i++) {
auto rating = ratings[i];
right.erase(right.find(rating));
auto l_it = lower_bound(left.begin(), left.end(), rating);
if (l_it != left.begin()) {
// the largest left that is strictly less than rating
l_it--;
auto left_count = distance(left.begin(), l_it) +1;
// the smallest right that is strictly more than rating
auto r_it = upper_bound(right.begin(), right.end(), rating);
auto right_count = distance(r_it, right.end());
ret += (left_count*right_count);
}
left.insert(rating);
}
return ret;
}
int numTeams(vector<int>& rating) {
int forward = solve(rating);
reverse(rating.begin(), rating.end());
int backward = solve(rating);
return forward + backward;
}
};
```