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] <= 105
• 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$.

• Java
• C++
• Python
• Go
• TypeScript

• 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;
  }
  
  

All Problems

All Solutions