LeetCode 1395 - Count Number of Teams

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Binary Indexed Tree, Segment Tree

Solution

Problem Understanding

The problem asks us to count the number of valid teams of three soldiers from a line of n soldiers, where each soldier has a unique rating. A valid team consists of three indices (i, j, k) such that the ratings are strictly increasing (rating[i] < rating[j] < rating[k]) or strictly decreasing (rating[i] > rating[j] > rating[k]) with 0 <= i < j < k < n.

The input is a list of integers representing soldier ratings. The output is a single integer representing the number of valid teams. Constraints indicate that the number of soldiers n can go up to 1000, and each rating is unique between 1 and 100,000.

Key observations include that the uniqueness of ratings simplifies comparisons, and the moderate size of n allows for quadratic algorithms. Edge cases include the smallest input (n=3), already sorted sequences (all increasing or decreasing), and sequences that allow no valid teams.

Approaches

The brute-force approach is straightforward: generate all possible triplets (i, j, k) and count those that satisfy the increasing or decreasing condition. This guarantees correctness because it checks every combination. However, it has a cubic time complexity (O(n^3)) which is too slow for n = 1000 because it results in up to 1 billion iterations.

The optimal approach uses the insight that we can treat each soldier as the middle member of the triplet (i, j, k). For each rating[j], we count how many smaller and larger ratings exist to its left (i < j) and to its right (k > j). The number of increasing teams with rating[j] in the middle is the product of the smaller ratings to the left and larger ratings to the right. Similarly, the number of decreasing teams is the product of larger ratings to the left and smaller ratings to the right. Summing this for all j yields the total number of valid teams. This reduces the complexity to O(n^2) with O(1) extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Check all triplets `(i, j, k)`
Optimal	O(n^2)	O(1)	Count smaller/larger elements to the left/right for each middle element

Algorithm Walkthrough

Initialize a variable count to store the number of valid teams.
Iterate over each soldier index j from 0 to n-1 treating it as the middle element of a triplet.
For the current rating[j], initialize four counters: left_smaller, left_larger, right_smaller, and right_larger.
Loop over all indices i less than j to count left_smaller (ratings less than rating[j]) and left_larger (ratings greater than rating[j]).
Loop over all indices k greater than j to count right_smaller (ratings less than rating[j]) and right_larger (ratings greater than rating[j]).
Compute the number of valid teams with rating[j] as middle:

Increasing: left_smaller * right_larger
Decreasing: left_larger * right_smaller

Add both to count.
After all iterations, return count.

Why it works: Every valid triplet has a middle element. By counting possible left and right candidates for each middle element, we enumerate all valid teams efficiently without redundant checking.

Python Solution

from typing import List

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        count = 0
        
        for j in range(n):
            left_smaller = left_larger = right_smaller = right_larger = 0
            
            for i in range(j):
                if rating[i] < rating[j]:
                    left_smaller += 1
                elif rating[i] > rating[j]:
                    left_larger += 1
            
            for k in range(j+1, n):
                if rating[k] < rating[j]:
                    right_smaller += 1
                elif rating[k] > rating[j]:
                    right_larger += 1
            
            count += left_smaller * right_larger + left_larger * right_smaller
        
        return count

The implementation follows the algorithm step by step. For each element treated as the middle of a triplet, it counts how many elements are smaller and larger to the left and right. The total valid teams are calculated using the product of the appropriate counts. No additional data structures are needed.

Go Solution

func numTeams(rating []int) int {
    n := len(rating)
    count := 0
    
    for j := 0; j < n; j++ {
        leftSmaller, leftLarger, rightSmaller, rightLarger := 0, 0, 0, 0
        
        for i := 0; i < j; i++ {
            if rating[i] < rating[j] {
                leftSmaller++
            } else if rating[i] > rating[j] {
                leftLarger++
            }
        }
        
        for k := j + 1; k < n; k++ {
            if rating[k] < rating[j] {
                rightSmaller++
            } else if rating[k] > rating[j] {
                rightLarger++
            }
        }
        
        count += leftSmaller*rightLarger + leftLarger*rightSmaller
    }
    
    return count
}

The Go implementation mirrors the Python solution. The main differences are syntax: explicit variable declarations and slice indexing. Since Go does not have List or len() methods like Python, we use len(rating) and standard integer arithmetic. Overflow is not a concern given constraints.

Worked Examples

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

j	left_smaller	left_larger	right_smaller	right_larger	Teams added
0	0	0	0	4	0
1	1	0	2	1	1_1 + 0_2 = 1
2	1	1	1	1	1_1 + 1_1 = 2
3	2	1	1	0	2_0 + 1_1 = 1
4	0	4	0	0	0

Total teams = 3

Example 2: rating = [2,1,3]

j	left_smaller	left_larger	right_smaller	right_larger
0	0	0	1	1
1	0	1	0	1
2	2	0	0	0

Total teams = 0

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

j	left_smaller	right_larger	Teams added
0	0	3	0
1	1	2	1*2 = 2
2	2	1	2*1 = 2
3	3	0	0

Total teams = 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	For each soldier as the middle element, we scan left and right arrays, giving `O(n*n)` operations.
Space	O(1)	Only counters are used, no extra data structures needed.

This O(n^2) solution is efficient for n <= 1000, resulting in at most 1 million iterations.

Test Cases

# Provided examples
assert Solution().numTeams([2,5,3,4,1]) == 3  # mix of increasing and decreasing teams
assert Solution().numTeams([2,1,3]) == 0       # no valid team
assert Solution().numTeams([1,2,3,4]) == 4     # all increasing

# Boundary cases
assert Solution().numTeams([1,2,3]) == 1       # minimum size n=3
assert Solution().numTeams([3,2,1]) == 1       # minimum size decreasing
assert Solution().numTeams([1,3,2]) == 0       # small array, no valid team

# Larger sequence
assert Solution().numTeams([5,1,3,2,4]) == 4   # mixed sequence
assert Solution().numTeams([1,4,2,3,