Count Number of Teams

mediumOA Simulation: 2 problems in 90 min each round55 stepsJava · Python · C++

Count triples i < j < k with strictly increasing or strictly decreasing ratings. Fix the middle soldier j: count smaller and larger ratings on each side. Increasing teams = smallerLeft × largerRight, decreasing = largerLeft × smallerRight.

▶ Watch the animated trace

Traced input: rating = [2, 5, 3, 4, 1] → 3. Original problem: leetcode.com/problems/count-number-of-teams/

Complexity

BestO(n²)

AverageO(n²)

WorstO(n²)

SpaceO(1)

A Fenwick tree brings it to O(n log n).

Key idea

Every team has exactly one middle member.
For a fixed middle, left and right choices are independent, so multiply.
Ratings are distinct, so 'smaller' and 'larger' cover everything.

Common mistakes

Triple loops are O(n³).
Counting only increasing teams.

Solution

Java

int numTeams(int[] rating) {
    int n = rating.length, teams = 0;
    for (int j = 1; j < n - 1; j++) {
        int lessL = 0, moreL = 0, lessR = 0, moreR = 0;
        for (int i = 0; i < j; i++) {
            if (rating[i] < rating[j]) lessL++;
            else moreL++;
        }
        for (int k = j + 1; k < n; k++) {
            if (rating[k] < rating[j]) lessR++;
            else moreR++;
        }
        teams += lessL * moreR + moreL * lessR;
    }
    return teams;
}

Python

def numTeams(rating: List[int]) -> int:
    n, teams = len(rating), 0
    for j in range(1, n - 1):
        less_l = sum(1 for i in range(j) if rating[i] < rating[j])
        more_l = j - less_l
        less_r = sum(1 for k in range(j + 1, n) if rating[k] < rating[j])
        more_r = n - 1 - j - less_r
        teams += less_l * more_r + more_l * less_r
    return teams

C++

int numTeams(vector<int>& rating) {
    int n = rating.size(), teams = 0;
    for (int j = 1; j < n - 1; j++) {
        int lessL = 0, moreL = 0, lessR = 0, moreR = 0;
        for (int i = 0; i < j; i++) {
            if (rating[i] < rating[j]) lessL++;
            else moreL++;
        }
        for (int k = j + 1; k < n; k++) {
            if (rating[k] < rating[j]) lessR++;
            else moreR++;
        }
        teams += lessL * moreR + moreL * lessR;
    }
    return teams;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
No teams Neither order works for the only triple.	`rating = [2, 1, 3]`	`0`
Strictly increasing Every triple: C(4, 3) = 4.	`rating = [1, 2, 3, 4]`	`4`
Fewer than three No middle soldier.	`rating = [1, 2]`	`0`