1395. Count Number of Teams

Problem Link

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.

Solution

---

C++

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int N = rating.size(), res = 0;
 
        for (int j = 1; j < N - 1; j++) {
            int leftSmaller = 0, leftBigger = 0;
 
            for (int i = 0; i < j; i++) {
                if (rating[i] < rating[j]) leftSmaller++;
                if (rating[i] > rating[j]) leftBigger++;
            }
 
            int rightSmaller = 0, rightBigger = 0;
            
            for (int k = j + 1; k < N; k++) {
                if (rating[k] > rating[j]) rightBigger++;
                if (rating[k] < rating[j]) rightSmaller++;
            }
 
            res += leftSmaller * rightBigger;
            res += leftBigger * rightSmaller;
        }
 
        return res;
    }
};

Python3

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        res = 0
        for i in range(len(rating)):
            ls = rs = lb = rb = 0
            
            for j in range(i-1,-1,-1):
                if rating[j] < rating[i]:
                    ls += 1
                elif rating[j] > rating[i]:
                    lb += 1
            
            for j in range(i+1,len(rating)):
                if rating[j] > rating[i]:
                    rb += 1
                elif rating[j] < rating[i]:
                    rs += 1
 
            res += ls*rb + lb*rs
        return res