Count Number of Teams - Solution & Explanation
Problem Statement
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.length3 <= n <= 10001 <= rating[i] <= 105- All the integers in
ratingare 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.
The brute force solution uses three nested loops to iterate over all possible triplets of indices (i, j, k) and checks if they form a valid team according to the given conditions.
Complexity
Time Complexity: O(n^3), where n is the length of the input array 'ratings'. This results from three nested loops each iterating over up to n elements.
Space Complexity: O(1), as it uses a constant amount of additional space.
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.
This C solution optimizes the number of checks by reducing it to O(n^2). It calculates the number of elements on the left and right of each soldier which are lesser or greater. These counts are then used to compute the number of valid teams involving that soldier.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(1)
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.
Code
Python
Java
C++
Go
TypeScript
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.
Code
Python
Java
C++
Go
TypeScript
Approach 5: Recursion + Memoization
Code
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), where n is the length of the input array 'ratings'. This results from three nested loops each iterating over up to n elements. Space Complexity: O(1), as it uses a constant amount of additional space. |
| Optimized Counting Approach | Time Complexity: O(n^2) Space Complexity: O(1) |
| Enumerate Middle Element | — |
| Binary Indexed Tree | — |
| Recursion + Memoization | — |
Detailed 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 |
Video Solution
Count Number of Teams - Leetcode 1395 - Python • NeetCodeIO • 16,555 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Number of Teams easy or hard?
Count Number of Teams Python/Java solution
How to solve Count Number of Teams in O(n^2)?
What is the best approach for Count Number of Teams?
Is Count Number of Teams asked at Google/Amazon/Meta?
What data structure is used in Count Number of Teams?
What is the time complexity of Count Number of Teams?
Ready to solve this problem?
Practice Count Number of Teams with our built-in code editor and test cases.
Practice on FleetCode