Count Number of Teams

Medium
586.

Count Number of Teams

Count Number of Teams is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

There are n soldiers standing in a line with distinct ratings.

A team is a triple of indices i < j < k whose ratings are either strictly increasing (rating[i] < rating[j] < rating[k]) or strictly decreasing.

Return the number of such teams.

Example 1

Input
rating = [2,5,3,4,1]
Output
3
Explanation
(2,3,4), (5,4,1) and (5,3,1).

Example 2

Input
rating = [2,1,3]
Output
0

Example 3

Input
rating = [1,2,3,4]
Output
4

Constraints

  • 3 <= rating.length <= 1000
  • 1 <= rating[i] <= 100000
  • All ratings are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} rating
 * @return {number}
 */
var numTeams = function(rating) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Number of Teams — Solution in Python, Java & C++

Count Number of Teams solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Number of Teams is a medium coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are n soldiers standing in a line with distinct ratings.

A team is a triple of indices i < j < k whose ratings are either strictly increasing (rating[i] < rating[j] < rating[k]) or strictly decreasing.

Return the number of such teams.

Example 1

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: (2,3,4), (5,4,1) and (5,3,1).

Example 2

Input: rating = [2,1,3]
Output: 0

Example 3

Input: rating = [1,2,3,4]
Output: 4

Constraints

  • 3 <= rating.length <= 1000
  • 1 <= rating[i] <= 100000
  • All ratings are distinct.

Hints for Count Number of Teams

  1. Hint 1

    Enumerating all triples is O(n³) — too slow at n = 1000.

  2. Hint 2

    Fix the middle soldier instead, and count what is available on each side.

  3. Hint 3

    An increasing team through j is (smaller on the left) × (larger on the right); the decreasing case mirrors it.

How to solve Count Number of Teams

Pivot on the middle element. Once j is fixed, the ends are independent, so the count is a product of two simple tallies.

Approach

  1. For each index j, count how many earlier ratings are smaller (lessLeft) and larger (moreLeft).
  2. Count how many later ratings are smaller (lessRight) and larger (moreRight).
  3. Add lessLeft * moreRight (increasing) plus moreLeft * lessRight (decreasing).
  4. Sum over every j.

Why it works

Every valid triple has exactly one middle element, so pivoting on it counts each team once. Given j, any qualifying left choice can pair with any qualifying right choice, which is why the counts multiply.

Complexity

  • Time — O(n²)
  • Space — O(1)

Pitfalls

  • Pivoting on the first or last element makes the two sides dependent and breaks the product.
  • Ratings are distinct, so < and > partition the comparisons — no equality case to handle.
  • The totals stay well inside 32 bits at n = 1000.

Reference solution

Python

from typing import List

def numTeams(rating: List[int]) -> int:
    n = len(rating)
    total = 0
    for j in range(n):
        less_left = sum(1 for i in range(j) if rating[i] < rating[j])
        more_left = j - less_left
        less_right = sum(1 for k in range(j + 1, n) if rating[k] < rating[j])
        more_right = (n - j - 1) - less_right
        total += less_left * more_right + more_left * less_right
    return total

Java

public static int numTeams(int[] rating) {
    int n = rating.length;
    int total = 0;
    for (int j = 0; j < n; j++) {
        int lessLeft = 0, moreLeft = 0, lessRight = 0, moreRight = 0;
        for (int i = 0; i < j; i++) {
            if (rating[i] < rating[j]) lessLeft++;
            else if (rating[i] > rating[j]) moreLeft++;
        }
        for (int k = j + 1; k < n; k++) {
            if (rating[k] < rating[j]) lessRight++;
            else if (rating[k] > rating[j]) moreRight++;
        }
        total += lessLeft * moreRight + moreLeft * lessRight;
    }
    return total;
}

C++

int numTeams(vector<int>& rating) {
    int n = (int) rating.size();
    int total = 0;
    for (int j = 0; j < n; j++) {
        int lessLeft = 0, moreLeft = 0, lessRight = 0, moreRight = 0;
        for (int i = 0; i < j; i++) {
            if (rating[i] < rating[j]) lessLeft++;
            else if (rating[i] > rating[j]) moreLeft++;
        }
        for (int k = j + 1; k < n; k++) {
            if (rating[k] < rating[j]) lessRight++;
            else if (rating[k] > rating[j]) moreRight++;
        }
        total += lessLeft * moreRight + moreLeft * lessRight;
    }
    return total;
}

JavaScript

var numTeams = function(rating) {
    const n = rating.length;
    let total = 0;
    for (let j = 0; j < n; j++) {
        let lessLeft = 0, moreLeft = 0, lessRight = 0, moreRight = 0;
        for (let i = 0; i < j; i++) {
            if (rating[i] < rating[j]) lessLeft++;
            else if (rating[i] > rating[j]) moreLeft++;
        }
        for (let k = j + 1; k < n; k++) {
            if (rating[k] < rating[j]) lessRight++;
            else if (rating[k] > rating[j]) moreRight++;
        }
        total += lessLeft * moreRight + moreLeft * lessRight;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming