Count Number of Teams
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward approach. We can generate all possible triplets of soldiers (i, j, k) such that 0 <= i < j < k < n using three nested loops. For each triplet, we check if their ratings satisfy the condition for a valid team: rating[i] < rating[j] < rating[k] (increasing) or rating[i] > rating[j] > rating[k] (decreasing). If the condition is met, we increment a counter.
Algorithm
- Initialize a counter
teamsto 0. - Use a loop for the first soldier
ifrom0ton-3. - Inside this loop, use a nested loop for the second soldier
jfromi+1ton-2. - Inside the second loop, use another nested loop for the third soldier
kfromj+1ton-1. - Within the innermost loop, check if
rating[i] < rating[j] && rating[j] < rating[k]. If true, incrementteams. - Also, check if
rating[i] > rating[j] && rating[j] > rating[k]. If true, incrementteams. - After all loops complete, return
teams.
Walkthrough
The brute-force method systematically checks every possible combination of three distinct soldiers. It uses three nested loops to select indices i, j, and k ensuring that i < j < k. For each valid combination of indices, it fetches their ratings and checks if they form a strictly increasing or strictly decreasing sequence. A counter is maintained to keep track of the number of valid teams found.
class Solution { public int numTeams(int[] rating) { int n = rating.length; if (n < 3) { return 0; } int teams = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (rating[i] < rating[j] && rating[j] < rating[k]) { teams++; } if (rating[i] > rating[j] && rating[j] > rating[k]) { teams++; } } } } return teams; }}Complexity
Time
O(n^3). Three nested loops iterate through all possible triplets, where `n` is the number of soldiers. For `n=1000`, this would be approximately `10^9` operations, which is too slow for typical time limits.
Space
O(1). We only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient and will likely result in a "Time Limit Exceeded" error for the given constraints (n <= 1000).
Solutions
Solution
class Solution {public int numTeams(int[] rating) { int n = rating.length; int ans = 0; for (int i = 0; i < n; ++i) { int l = 0, r = 0; for (int j = 0; j < i; ++j) { if (rating[j] < rating[i]) { ++l; } } for (int j = i + 1; j < n; ++j) { if (rating[j] > rating[i]) { ++r; } } ans += l * r; ans += (i - l) * (n - i - 1 - r); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.