Watch 10 video solutions for Count Number of Teams, a medium level problem involving Array, Dynamic Programming, Binary Indexed Tree. This walkthrough by NeetCodeIO has 16,209 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
i, j, k) with rating (rating[i], rating[j], rating[k]).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] <= 105rating are unique.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 | 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 |