Count number of teams

Array Dynamic Programming Binary Indexed Tree Segment Tree

70.2% acceptance

Feb 25, 2026

3448

237

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

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn num_teams(rating: Vec<i32>) -> i32 {
    let n = rating.len();
    let mut count = 0;
    for j in 1..n-1 {
      let (mut li, mut lj, mut ri, mut rj) = (0, 0, 0, 0);
      for i in 0..j {
        if rating[i] < rating[j] { li += 1; }
        if rating[i] > rating[j] { lj += 1; }
      }
      for k in j+1..n {
        if rating[k] > rating[j] { ri += 1; }
        if rating[k] < rating[j] { rj += 1; }
      }
      count += li * ri + lj * rj;
    }
    count
  }
}