1395. Count Number of Teams - Solution

The problem

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] <= 10⁵
All the integers in rating are unique.

Approach overview

Problem Overview: You are given an array rating where each value represents a soldier’s rating. A valid team consists of three soldiers (i, j, k) with i < j < k such that ratings are strictly increasing rating[i] < rating[j] < rating[k] or strictly decreasing rating[i] > rating[j] > rating[k]. The task is to count how many such teams exist.

Approach 1: Brute Force (O(n^3) time, O(1) space)

The straightforward solution checks every possible triple of indices. Use three nested loops: pick i, then j > i, then k > j. For each triplet, verify whether the ratings form a strictly increasing or strictly decreasing sequence. This approach is easy to implement and clearly expresses the constraints of the problem. However, the cubic time complexity becomes slow when the array size grows, making it unsuitable for large inputs.

Approach 2: Optimized Counting with Middle Element (O(n^2) time, O(1) space)

Instead of enumerating all triples, treat each element as the middle soldier of the team. For an index j, count how many elements to the left are smaller and larger than rating[j], and how many elements to the right are smaller and larger. If leftLess soldiers are smaller on the left and rightGreater are larger on the right, they form increasing teams: leftLess * rightGreater. Similarly, decreasing teams come from leftGreater * rightLess. Iterate through the array and compute these counts by scanning both sides. This reduces the problem to pair counting and removes the innermost loop.

Approach 3: Binary Indexed Tree / Segment Tree (O(n log n) time, O(n) space)

For larger constraints, you can accelerate the counting using a Binary Indexed Tree or a Segment Tree. Maintain prefix frequency counts of ratings as you scan the array. These structures allow efficient queries such as “how many elements smaller than x have appeared so far.” Combine prefix counts (left side) and suffix counts (right side) to compute increasing and decreasing teams in logarithmic time per element. This approach is more advanced but scales better when rating values are large.

The optimized counting strategy relies mainly on careful iteration over an array and reasoning about relative order rather than brute enumeration. The pattern also appears in several ranking and triplet-counting problems.

Recommended for interviews: The O(n^2) middle-element counting approach. It demonstrates that you recognized the structure of increasing/decreasing triplets and eliminated redundant checks. Mentioning the brute force approach shows baseline understanding, while the optimized counting method proves you can improve complexity through better counting logic.

Approach 1: Brute Force Approach

This approach involves checking all possible combinations of three soldiers using nested loops to see if they can form a valid team. Although simple, this approach can be optimized by ensuring we scoot to the inner loops only when conditions are satisfied.

Python

def numTeams(rating):
    count = 0
    n = len(rating)
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                if (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]):
                    count += 1
    return count

ratings = [2, 5, 3, 4, 1]
print(numTeams(ratings)) # Output: 3

Java

import java.util.*;

public class Main {
    public static int numTeams(int[] rating) {
        int count = 0;
        int n = rating.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
                        (rating[i] > rating[j] && rating[j] > rating[k])) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] ratings = {2, 5, 3, 4, 1};
        System.out.println(numTeams(ratings)); // Output: 3
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int numTeams(vector<int>& rating) {
    int count = 0;
    int n = rating.size();
    for (int i = 0; i < n - 2; ++i) {
        for (int j = i + 1; j < n - 1; ++j) {
            for (int k = j + 1; k < n; ++k) {
                if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
                    (rating[i] > rating[j] && rating[j] > rating[k])) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    vector<int> ratings = {2, 5, 3, 4, 1};
    cout << numTeams(ratings) << endl; // Output: 3
    return 0;
}

JavaScript

function numTeams(rating) {
    let count = 0;
    let n = rating.length;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
                    (rating[i] > rating[j] && rating[j] > rating[k])) {
                    count++;
                }
            }
        }
    }
    return count;
}

const ratings = [2, 5, 3, 4, 1];
console.log(numTeams(ratings)); // Output: 3

#include <stdio.h>

int numTeams(int* rating, int ratingSize) {
    int count = 0;
    for (int i = 0; i < ratingSize - 2; i++) {
        for (int j = i + 1; j < ratingSize - 1; j++) {
            for (int k = j + 1; k < ratingSize; k++) {
                if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
                    (rating[i] > rating[j] && rating[j] > rating[k])) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    int ratings[] = {2, 5, 3, 4, 1};
    int size = sizeof(ratings) / sizeof(ratings[0]);
    printf("%d\n", numTeams(ratings, size)); // Output: 3
    return 0;
}

using System;

class Program {
    public static int NumTeams(int[] rating) {
        int count = 0;
        int n = rating.Length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
                        (rating[i] > rating[j] && rating[j] > rating[k])) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    static void Main(string[] args) {
        int[] ratings = { 2, 5, 3, 4, 1 };
        Console.WriteLine(NumTeams(ratings)); // Output: 3
    }
}

This Python implementation uses three nested loops to generate all possible triplet indices and checks for valid team formations.

Complexity

Time Complexity: O(n^3)

Space Complexity: O(1)

Try this approach in the editor

Approach 2: Optimized Counting Approach

This approach reduces the number of nested loops from three to two by counting the number of elements to the left and right that satisfy the increasing or decreasing condition required for forming a team.

Python

def numTeams(rating):
    count = 0
    n = len(rating)
    for j in range(n):
        less_left = greater_left = less_right = greater_right = 0
        for i in range(j):
            if rating[i] < rating[j]:
                less_left += 1
            elif rating[i] > rating[j]:
                greater_left += 1
        for k in range(j + 1, n):
            if rating[j] < rating[k]:
                less_right += 1
            elif rating[j] > rating[k]:
                greater_right += 1
        count += less_left * less_right + greater_left * greater_right
    return count

ratings = [2, 5, 3, 4, 1]
print(numTeams(ratings)) # Output: 3

Java

import java.util.*;

public class Main {
    public static int numTeams(int[] rating) {
        int count = 0;
        int n = rating.length;
        for (int j = 0; j < n; j++) {
            int less_left = 0, greater_left = 0, less_right = 0, greater_right = 0;
            for (int i = 0; i < j; i++) {
                if (rating[i] < rating[j]) less_left++;
                else if (rating[i] > rating[j]) greater_left++;
            }
            for (int k = j + 1; k < n; k++) {
                if (rating[j] < rating[k]) less_right++;
                else if (rating[j] > rating[k]) greater_right++;
            }
            count += less_left * less_right + greater_left * greater_right;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] ratings = {2, 5, 3, 4, 1};
        System.out.println(numTeams(ratings)); // Output: 3
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int numTeams(vector<int>& rating) {
    int count = 0;
    int n = rating.size();
    for (int j = 0; j < n; j++) {
        int less_left = 0, greater_left = 0, less_right = 0, greater_right = 0;
        for (int i = 0; i < j; i++) {
            if (rating[i] < rating[j]) less_left++;
            else if (rating[i] > rating[j]) greater_left++;
        }
        for (int k = j + 1; k < n; k++) {
            if (rating[j] < rating[k]) less_right++;
            else if (rating[j] > rating[k]) greater_right++;
        }
        count += less_left * less_right + greater_left * greater_right;
    }
    return count;
}

int main() {
    vector<int> ratings = {2, 5, 3, 4, 1};
    cout << numTeams(ratings) << endl; // Output: 3
    return 0;
}

JavaScript

function numTeams(rating) {
    let count = 0;
    const n = rating.length;
    for (let j = 0; j < n; j++) {
        let less_left = 0, greater_left = 0, less_right = 0, greater_right = 0;
        for (let i = 0; i < j; i++) {
            if (rating[i] < rating[j]) less_left++;
            else if (rating[i] > rating[j]) greater_left++;
        }
        for (let k = j + 1; k < n; k++) {
            if (rating[j] < rating[k]) less_right++;
            else if (rating[j] > rating[k]) greater_right++;
        }
        count += less_left * less_right + greater_left * greater_right;
    }
    return count;
}

const ratings = [2, 5, 3, 4, 1];
console.log(numTeams(ratings)); // Output: 3

#include <stdio.h>

int numTeams(int* rating, int ratingSize) {
    int count = 0;
    for (int j = 0; j < ratingSize; j++) {
        int less_left = 0, greater_left = 0, less_right = 0, greater_right = 0;
        for (int i = 0; i < j; i++) {
            if (rating[i] < rating[j]) less_left++;
            else if (rating[i] > rating[j]) greater_left++;
        }
        for (int k = j + 1; k < ratingSize; k++) {
            if (rating[j] < rating[k]) less_right++;
            else if (rating[j] > rating[k]) greater_right++;
        }
        count += less_left * less_right + greater_left * greater_right;
    }
    return count;
}

int main() {
    int ratings[] = {2, 5, 3, 4, 1};
    int size = sizeof(ratings) / sizeof(ratings[0]);
    printf("%d\n", numTeams(ratings, size)); // Output: 3
    return 0;
}

using System;

class Program {
    public static int NumTeams(int[] rating) {
        int count = 0;
        int n = rating.Length;
        for (int j = 0; j < n; j++) {
            int less_left = 0, greater_left = 0, less_right = 0, greater_right = 0;
            for (int i = 0; i < j; i++) {
                if (rating[i] < rating[j]) less_left++;
                else if (rating[i] > rating[j]) greater_left++;
            }
            for (int k = j + 1; k < n; k++) {
                if (rating[j] < rating[k]) less_right++;
                else if (rating[j] > rating[k]) greater_right++;
            }
            count += less_left * less_right + greater_left * greater_right;
        }
        return count;
    }
    
    static void Main(string[] args) {
        int[] ratings = {2, 5, 3, 4, 1};
        Console.WriteLine(NumTeams(ratings)); // Output: 3
    }
}

The Python solution efficiently calculates the number of valid teams by considering each potential middle soldier and counting appropriate soldiers on both sides.

Complexity

Time Complexity: O(n^2)

Space Complexity: O(1)

Try this approach in the editor

Approach 3: 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.

TypeScript

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

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
}

Try this approach in the editor

Approach 4: 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.

TypeScript

class BinaryIndexedTree {
    private n: number;
    private c: number[];

    constructor(n: number) {
        this.n = n;
        this.c = new Array(n + 1).fill(0);
    }

    public update(x: number, v: number): void {
        while (x <= this.n) {
            this.c[x] += v;
            x += x & -x;
        }
    }

    public query(x: number): number {
        let s = 0;
        while (x > 0) {
            s += this.c[x];
            x -= x & -x;
        }
        return s;
    }
}

function numTeams(rating: number[]): number {
    let nums = [...rating];
    nums.sort((a, b) => a - b);
    const n = rating.length;
    let m = 0;
    for (let i = 0; i < n; ++i) {
        if (i === 0 || nums[i] !== nums[i - 1]) {
            nums[m++] = nums[i];
        }
    }
    nums = nums.slice(0, m);
    const search = (x: number): number => {
        let l = 0;
        let r = m;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (nums[mid] >= x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l + 1;
    };
    let ans = 0;
    const tree1 = new BinaryIndexedTree(m);
    const tree2 = new BinaryIndexedTree(m);
    for (const x of rating) {
        tree2.update(search(x), 1);
    }
    for (let i = 0; i < n; ++i) {
        const x = search(rating[i]);
        tree1.update(x, 1);
        tree2.update(x, -1);
        const l = tree1.query(x - 1);
        const r = n - i - 1 - tree2.query(x);
        ans += l * r;
        ans += (i - l) * (n - i - 1 - r);
    }
    return ans;
}

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += x & -x
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= x & -x
	}
	return s
}

func numTeams(rating []int) (ans int) {
	nums := make([]int, len(rating))
	copy(nums, rating)
	sort.Ints(nums)
	m := 0
	for i, x := range nums {
		if i == 0 || x != nums[i-1] {
			nums[m] = x
			m++
		}
	}
	nums = nums[:m]
	tree1 := newBinaryIndexedTree(m)
	tree2 := newBinaryIndexedTree(m)
	for _, x := range rating {
		tree2.update(sort.SearchInts(nums, x)+1, 1)
	}
	n := len(rating)
	for i, v := range rating {
		x := sort.SearchInts(nums, v) + 1
		tree1.update(x, 1)
		tree2.update(x, -1)
		l := tree1.query(x - 1)
		r := n - i - 1 - tree2.query(x)
		ans += l * r
		ans += (i - l) * (n - i - 1 - r)
	}
	return
}

Try this approach in the editor

Approach 5: Recursion + Memoization

TypeScript

function numTeams(rating: number[]): number {
    const n = rating.length;
    const f: Record<Type, number[][]> = {
        asc: Array.from({ length: n }, () => Array(3).fill(-1)),
        desc: Array.from({ length: n }, () => Array(3).fill(-1)),
    };

    const fn = (i: number, available: number, type: Type) => {
        if (!available) {
            return 1;
        }
        if (f[type][i][available] !== -1) {
            return f[type][i][available];
        }

        let ans = 0;
        for (let j = i + 1; j < n; j++) {
            if (rating[j] > rating[i]) {
                if (type === 'asc') {
                    ans += fn(j, available - 1, 'asc');
                }
            } else {
                if (type === 'desc') {
                    ans += fn(j, available - 1, 'desc');
                }
            }
        }
        f[type][i][available] = ans;

        return ans;
    };

    let ans = 0;
    for (let i = 0; i < n; i++) {
        ans += fn(i, 2, 'asc') + fn(i, 2, 'desc');
    }

    return ans;
}

type Type = 'asc' | 'desc';

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Approach	Time Complexity: O(n^3) Space Complexity: O(1)
Optimized Counting Approach	Time Complexity: O(n^2) Space Complexity: O(1)
Enumerate Middle Element	–
Binary Indexed Tree	–
Recursion + Memoization	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Triplets	O(n^3)	O(1)	Useful for understanding the problem or when input size is very small
Middle Element Counting	O(n^2)	O(1)	Best balance of simplicity and efficiency; common interview solution
Binary Indexed Tree / Segment Tree	O(n log n)	O(n)	When ratings range is large and faster counting queries are needed

Frequently asked questions

Is Count Number of Teams easy or hard?

Count Number of Teams is classified as a medium problem. The brute force idea is simple, but recognizing that the middle element can be used to count increasing and decreasing triplets efficiently requires stronger algorithmic thinking.

Count Number of Teams Python/Java solution

Python and Java implementations typically follow the O(n^2) counting strategy. Iterate through each index as the middle element, compute counts of smaller and larger elements on both sides, and accumulate valid combinations. The same logic translates easily across Python, Java, C++, and other languages.

How to solve Count Number of Teams in O(n^2)?

Iterate through the array and treat each element as the middle soldier. Count how many ratings on the left are smaller and larger than it, and do the same for the right side. Increasing teams are formed by leftSmaller × rightGreater, while decreasing teams are leftGreater × rightSmaller. Summing these counts for every index produces the final answer in O(n^2) time.

What is the best approach for Count Number of Teams?

The most practical approach is the O(n^2) middle-element counting technique. For each index j, count how many elements on the left are smaller or larger than rating[j], and how many on the right are smaller or larger. Multiply the counts to form increasing and decreasing teams. This removes the third loop from the brute force solution while keeping the implementation simple.

Is Count Number of Teams asked at Google/Amazon/Meta?

Triplet counting and ranking problems similar to Count Number of Teams appear in interviews at companies like Amazon, Google, and Meta. The problem tests array traversal, counting logic, and the ability to optimize from brute force to more efficient solutions.

What data structure is used in Count Number of Teams?

The core solution works directly on arrays with simple counting logic. For optimized variants, Binary Indexed Trees (Fenwick Trees) or Segment Trees can be used to maintain prefix frequency counts and answer order queries efficiently.

What is the time complexity of Count Number of Teams?

The brute force approach runs in O(n^3) time because it checks every combination of three soldiers. The commonly accepted optimized solution runs in O(n^2) time by fixing the middle soldier and counting valid pairs around it. With advanced data structures like Binary Indexed Trees, the complexity can be reduced to O(n log n).

Count Number of Teams solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Counting Approach

Approach 3: Enumerate Middle Element

Approach 4: Binary Indexed Tree

Approach 5: Recursion + Memoization

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Number of Teams solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Counting Approach

Approach 3: Enumerate Middle Element

Approach 4: Binary Indexed Tree

Approach 5: Recursion + Memoization

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems