#1395

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Number of Teams

Count the number of valid three-soldier teams using ratings with a state transition dynamic programming approach efficiently.

array dynamic programming binary indexed tree segment tree

Problem Statement

You are given an array representing the ratings of n soldiers standing in a line. Each soldier has a unique rating, and you want to form teams of exactly three soldiers that follow specific rating rules.

A team is valid if the ratings of the three chosen soldiers are strictly increasing or strictly decreasing according to their positions in the array. Return the total number of valid teams that can be formed. Note that a soldier may belong to multiple teams.

Examples

Example 1

Input: rating = [2,5,3,4,1]

Output: 3

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

We can't form any team given the conditions.

Example 3

Input: rating = [1,2,3,4]

Output: 4

Example details omitted.

Constraints

n == rating.length
3 <= n <= 1000
1 <= rating[i] <= 105
All the integers in rating are unique.

Solution Approach

Brute-force enumeration

Iterate over all triplets of soldiers and check if their ratings form a strictly increasing or decreasing sequence. This method is simple but inefficient for larger arrays, as it has O(n^3) time complexity.

State transition dynamic programming

Use DP arrays to store the number of smaller and larger ratings before and after each soldier. For each position, calculate potential teams using the counts of preceding and succeeding soldiers with appropriate ratings. This reduces complexity significantly compared to brute-force.

Optimized counting with Binary Indexed Tree

Leverage a Binary Indexed Tree or Segment Tree to maintain prefix and suffix counts efficiently. Update and query the number of smaller and larger ratings in logarithmic time to calculate the total number of valid teams, achieving O(n log(maxRating)) time complexity.

Complexity Analysis

Metric	Value
Time	O(n \cdot \log(\text{maxRating}))
Space	O(\text{maxRating})

The optimized approach uses O(n log(maxRating)) time due to BIT updates and queries, and O(maxRating) space for frequency arrays. Brute-force requires O(n^3) time, while simple DP without BIT uses O(n^2).

What Interviewers Usually Probe

Look for strictly increasing or decreasing sequences of length three.
Check if the candidate avoids brute-force cubic time by counting sequences efficiently.
Verify understanding of state transitions and prefix-suffix relationships for DP.

Common Pitfalls or Variants

Common pitfalls

Counting teams incorrectly by mixing indices instead of ratings order.
Using nested loops without considering DP or BIT optimizations for larger arrays.
Mismanaging prefix and suffix counts, leading to off-by-one errors in team totals.

Follow-up variants

Count teams of length k > 3 following increasing or decreasing rules.
Compute total teams allowing repeated ratings with adjusted DP rules.
Find the longest strictly increasing or decreasing subsequence instead of fixed-length teams.

FAQ

What is the main approach to solve Count Number of Teams efficiently?

The most efficient method uses state transition dynamic programming combined with prefix and suffix counts to calculate all valid three-soldier teams.

Can I use a brute-force approach?

Yes, but brute-force has O(n^3) complexity and will be too slow for arrays close to 1000 elements.

Why are Binary Indexed Trees useful for this problem?

BITs allow you to maintain prefix and suffix counts of smaller or larger ratings efficiently, reducing overall computation from O(n^2) to O(n log(maxRating)).

Are soldiers allowed in multiple teams?

Yes, each soldier can be part of multiple valid teams as long as the sequence rules are satisfied.

What are common mistakes when implementing DP for this pattern?

Typical mistakes include miscounting prefix or suffix arrays, confusing index order with rating order, or forgetting to handle both increasing and decreasing sequences.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans, n = 0, len(rating)
        for i, b in enumerate(rating):
            l = sum(a < b for a in rating[:i])
            r = sum(c > b for c in rating[i + 1 :])
            ans += l * r
            ans += (i - l) * (n - i - 1 - r)
        return ans

Solution 2: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans, n = 0, len(rating)
        for i, b in enumerate(rating):
            l = sum(a < b for a in rating[:i])
            r = sum(c > b for c in rating[i + 1 :])
            ans += l * r
            ans += (i - l) * (n - i - 1 - r)
        return ans

Solution 3: Recursion + Memoization

#### TypeScript

1

2

3

4

5

6

7

8

9

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        ans, n = 0, len(rating)
        for i, b in enumerate(rating):
            l = sum(a < b for a in rating[:i])
            r = sum(c > b for c in rating[i + 1 :])
            ans += l * r
            ans += (i - l) * (n - i - 1 - r)
        return ans

Continue Practicing

#673 number of longest increasing subsequence #2407 longest increasing subsequence ii #1157 online majority element in subarray