Count the number of teams

Leetcode no. 1395

The problem statement is:

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 a 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).

SOLUTION-

When we first look into the problem, the simple approach we have is to have three nested loops for each i, j, and k and check for the condition. If satisfied, it will increment the number of teams. The solution will be somewhat like this:

class Solution {
public:
int numTeams(vector<int>& rating) {
int teams=0;
for(int i=0;i<rating.size();i++){
for(int j=i+1;j<rating.size();j++){
for(int k=j+1;k<rating.size();k++){
if((rating[i]>rating[j]&&rating[j]>rating[k])||(rating[i]<rating[j]&&rating[j]<rating[k]))
teams++;
}
}
}
return teams;
}
};

The complexity of the program above will be O(n³) due to the three loops we have incorporated.

The other way we can solve this problem is:

To have three variables and start the loop from the 1st position. The second variable can always be our present loop item. So, whenever we find any element smaller than the current, we increment variable1 and whenever we find element greater than our current after its own position, we increment variable. This way the complexity will be significantly reduced to O(n²).

We can code the same for the condition i>j>k also. The code will be like:

class Solution {
public:
int numTeams(vector<int>& rating) {
int teams=0;
for(int i=1;i<rating.size();i++){
int e1=0,e3=0,d1=0,d3=0;
for(int j=0;j<rating.size();j++){
if(j<i){
if(rating[j]<rating[i]){
e1++;
}
else{
d1++;
}
}
if(j>i){
if(rating[j]>rating[i]){
e3++;
}
else{
d3++;
}
}
}
teams+=(e1*e3);
teams+=(d1*d3);
}
return teams;
}
};

I hope you will find the solution helpful.