Problem Description

You are given an array of n soldiers standing in a line, where each soldier has a unique rating value.

Your task is to count how many teams of exactly 3 soldiers can be formed following these rules:

1. A team consists of 3 soldiers at positions i, j, and k where i < j < k
2. A team is valid if either:
   • The ratings are in ascending order: rating[i] < rating[j] < rating[k], OR
   • The ratings are in descending order: rating[i] > rating[j] > rating[k]

The same soldier can be part of multiple different teams.

For example, if you have ratings [2, 5, 3, 4, 1]:

• Team (2, 3, 4) at indices (0, 2, 3) is valid because 2 < 3 < 4
• Team (5, 3, 1) at indices (1, 2, 4) is valid because 5 > 3 > 1
• Team (5, 4, 1) at indices (1, 3, 4) is valid because 5 > 4 > 1

The solution works by fixing each soldier as the middle element of a potential team. For each middle soldier at position i with rating b:

• Count how many soldiers to the left have ratings less than b (call this l)
• Count how many soldiers to the right have ratings greater than b (call this r)
• This gives us l * r ascending teams with this middle soldier
• Similarly, (i - l) * (n - i - 1 - r) gives us descending teams with this middle soldier

The total number of valid teams is the sum of all such combinations across all possible middle soldiers.

Intuition

The key insight is that every valid team of 3 soldiers must have a middle element. Instead of trying to find all possible triplets directly (which would be O(n³)), we can fix the middle element and count how many valid teams can be formed with it.

Think about it this way: for any soldier in the middle position of a team, what determines if we can form valid teams?

For an ascending team (a, b, c) where b is our fixed middle element:

• We need one soldier on the left with rating less than b
• We need one soldier on the right with rating greater than b
• If we have l choices on the left and r choices on the right, we can form l * r different ascending teams

For a descending team (a, b, c) where b is our fixed middle element:

• We need one soldier on the left with rating greater than b
• We need one soldier on the right with rating less than b
• If there are i total soldiers to the left and l of them are smaller than b, then (i - l) are greater than b
• Similarly, if there are (n - i - 1) soldiers to the right and r of them are greater than b, then (n - i - 1 - r) are smaller than b
• So we can form (i - l) * (n - i - 1 - r) different descending teams

By iterating through each soldier as a potential middle element and counting both ascending and descending teams they can form, we avoid checking every possible triplet combination. This reduces our time complexity from O(n³) to O(n²) since for each of the n positions, we only need to count elements on the left and right once.

Learn more about Segment Tree and Dynamic Programming patterns.

Solution Approach

The implementation follows the enumerate middle element strategy described in the reference approach. Here's how the solution works step by step:

1. Initialize variables: Set ans = 0 to store the total count of teams, and get the length n of the rating array.

2. Enumerate each soldier as the middle element: Use enumerate(rating) to iterate through each soldier, getting both the index i and their rating value b.

3. Count smaller elements on the left:

   l = sum(a < b for a in rating[:i])

   This counts how many soldiers to the left of position i have ratings smaller than b.

4. Count larger elements on the right:

   r = sum(c > b for c in rating[i + 1:])

   This counts how many soldiers to the right of position i have ratings larger than b.

5. Calculate ascending teams:

   ans += l * r

   For ascending order teams (a, b, c) where a < b < c, we multiply the number of valid left choices l by the number of valid right choices r.

6. Calculate descending teams:

   ans += (i - l) * (n - i - 1 - r)

   For descending order teams (a, b, c) where a > b > c:

   • (i - l) gives the count of soldiers on the left with ratings greater than b
   • (n - i - 1 - r) gives the count of soldiers on the right with ratings smaller than b
   • Their product gives all possible descending teams with b as the middle element

7. Return the total count: After processing all possible middle elements, return ans.

The time complexity is O(n²) because for each of the n elements, we scan the array once to count elements on both sides. The space complexity is O(1) as we only use a few variables to store counts.

Example Walkthrough

Let's walk through a small example with rating = [2, 5, 3, 4, 1].

We'll fix each soldier as the middle element and count valid teams:

Step 1: Middle soldier at index 0 (rating = 2)

• Left side: [] (empty)
• Right side: [5, 3, 4, 1]
• Count smaller on left (l): 0
• Count larger on right (r): 3 (values 5, 3, 4 are all > 2)
• Ascending teams: 0 × 3 = 0
• Descending teams: (0 - 0) × (4 - 3) = 0 × 1 = 0
• Total so far: 0

Step 2: Middle soldier at index 1 (rating = 5)

• Left side: [2]
• Right side: [3, 4, 1]
• Count smaller on left (l): 1 (value 2 < 5)
• Count larger on right (r): 0 (no values > 5)
• Ascending teams: 1 × 0 = 0
• Descending teams: (1 - 1) × (3 - 0) = 0 × 3 = 0
• Total so far: 0

Step 3: Middle soldier at index 2 (rating = 3)

• Left side: [2, 5]
• Right side: [4, 1]
• Count smaller on left (l): 1 (value 2 < 3)
• Count larger on right (r): 1 (value 4 > 3)
• Ascending teams: 1 × 1 = 1 (team: 2-3-4)
• Descending teams: (2 - 1) × (2 - 1) = 1 × 1 = 1 (team: 5-3-1)
• Total so far: 0 + 1 + 1 = 2

Step 4: Middle soldier at index 3 (rating = 4)

• Left side: [2, 5, 3]
• Right side: [1]
• Count smaller on left (l): 2 (values 2, 3 < 4)
• Count larger on right (r): 0 (no values > 4)
• Ascending teams: 2 × 0 = 0
• Descending teams: (3 - 2) × (1 - 0) = 1 × 1 = 1 (team: 5-4-1)
• Total so far: 2 + 0 + 1 = 3

Step 5: Middle soldier at index 4 (rating = 1)

• Left side: [2, 5, 3, 4]
• Right side: [] (empty)
• Count smaller on left (l): 0 (no values < 1)
• Count larger on right (r): 0 (empty)
• Ascending teams: 0 × 0 = 0
• Descending teams: (4 - 0) × (0 - 0) = 4 × 0 = 0
• Total so far: 3

Final Answer: 3 teams

• Ascending: (2, 3, 4)
• Descending: (5, 3, 1) and (5, 4, 1)

Solution Implementation

Time and Space Complexity

The time complexity is O(n²) and the space complexity is O(1), where n is the length of the array rating.

Time Complexity Analysis:

• The outer loop iterates through each element in the rating array, which runs n times
• For each iteration i, we count elements less than rating[i] in rating[:i] which takes O(i) time
• We also count elements greater than rating[i] in rating[i+1:] which takes O(n-i-1) time
• The total time for iteration i is O(i) + O(n-i-1) = O(n)
• Since we do this for all n elements, the overall time complexity is O(n) × n = O(n²)

Space Complexity Analysis:

• The algorithm only uses a constant amount of extra space for variables ans, n, i, b, l, and r
• No additional data structures that grow with input size are created
• Therefore, the space complexity is O(1)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Index Calculations

A frequent mistake is incorrectly calculating the counts for descending teams. When computing greater_left and smaller_right, developers often forget to account for the exact position boundaries:

Incorrect approach:

# Wrong calculation for greater_left
greater_left = i - smaller_left - 1  # Incorrectly subtracts 1

# Wrong calculation for smaller_right
smaller_right = n - i - greater_right  # Forgets to subtract 1 for the current element

Correct approach:

# Correct: i elements to the left, smaller_left have smaller ratings
greater_left = i - smaller_left

# Correct: (n - i - 1) elements to the right, greater_right have greater ratings
smaller_right = (n - i - 1) - greater_right

2. Attempting to Find All Triplets Explicitly

Some developers try to use three nested loops to check all possible triplets:

Inefficient approach:

def numTeams(self, rating: List[int]) -> int:
    count = 0
    n = len(rating)
    for i in range(n):
        for j in range(i + 1, n):
            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

This has O(n³) time complexity and becomes inefficient for larger inputs.

3. Forgetting to Handle Both Ascending and Descending Cases

A common oversight is only counting one type of team:

Incomplete solution:

def numTeams(self, rating: List[int]) -> int:
    total_teams = 0
    n = len(rating)
  
    for i in range(n):
        current_rating = rating[i]
        smaller_left = sum(1 for r in rating[:i] if r < current_rating)
        greater_right = sum(1 for r in rating[i + 1:] if r > current_rating)
      
        # Only counts ascending teams, forgets descending teams!
        total_teams += smaller_left * greater_right
  
    return total_teams

4. Using Incorrect Comparison Operators

Mixing up strict inequalities with non-strict ones:

Wrong:

# Using <= instead of < will count equal ratings incorrectly
smaller_left = sum(1 for r in rating[:i] if r <= current_rating)

Correct:

# Must use strict inequality since all ratings are unique
smaller_left = sum(1 for r in rating[:i] if r < current_rating)

5. Not Leveraging the Uniqueness Constraint

The problem states each soldier has a unique rating. This means we don't need to handle equal ratings, simplifying our logic. Some solutions unnecessarily complicate the code by trying to handle equal ratings that won't exist.

Solution Tips:

• Always draw out the index boundaries on paper first
• Test with small examples like [1, 2, 3] and [3, 2, 1] to verify your counting logic
• Remember that when a soldier is fixed as the middle element, you're essentially counting valid pairs on each side that can combine with it