1395. Count Number of Teams

Question

LeetCode Problem

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

int numTeams(vector<int> &rating) {
	int m = rating.size();
	int result = 0;
	for (int j = 1; j < (m-1); ++j) {
		int middle = rating[j];
		int leftLessThanMiddle = 0;
		int leftMoreThanMiddle = 0;
		int rightLessThanMiddle = 0;
		int rightMoreThanMiddle = 0;
		for (int i = 0; i < j; ++i) {
			if (rating[i] < middle) leftLessThanMiddle += 1;
			if (rating[i] > middle) leftMoreThanMiddle += 1;
		}
		for (int k = j + 1; k < m; ++k) {
			if (rating[k] > middle) rightMoreThanMiddle += 1;
			if (rating[k] < middle) rightLessThanMiddle += 1;
		}
		result += leftLessThanMiddle * rightMoreThanMiddle + leftMoreThanMiddle * rightLessThanMiddle;
	}
	return result;
}