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 <= 10001 <= rating[i] <= 100000All ratings are distinct.
Hints for Count Number of Teams
Hint 1
Enumerating all triples is O(n³) — too slow at
n = 1000.Hint 2
Fix the middle soldier instead, and count what is available on each side.
Hint 3
An increasing team through
jis(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
- For each index
j, count how many earlier ratings are smaller (lessLeft) and larger (moreLeft). - Count how many later ratings are smaller (
lessRight) and larger (moreRight). - Add
lessLeft * moreRight(increasing) plusmoreLeft * lessRight(decreasing). - 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 totalJava
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