Count Number of Teams: Fix the Middle Element

Given an array rating of unique integers where rating[i] is the rating of the i-th soldier, count the number of teams of 3 soldiers (i, j, k) such that i < j < k and either rating[i] < rating[j] < rating[k] (increasing) or rating[i] > rating[j] > rating[k] (decreasing).

This is LeetCode 1395: Count Number of Teams, and it is an excellent problem for learning how to count triplets efficiently by fixing the middle element and combining contributions from both sides.

Why this problem matters

Brute force would check all O(n^3) triplets, which is too slow. This problem teaches a powerful counting technique: instead of iterating over all possible triplets, you fix one element and figure out how many valid configurations surround it. This "fix one, count the rest" pattern appears in many array counting problems, including problems about subsequences, pairs, and inversions.

Once you internalize the idea of fixing the middle element and multiplying left and right contributions, you will recognize it in problems like 3Sum, Number of Longest Increasing Subsequence, and 132 Pattern.

The key insight

The key insight is to fix the middle element. For each index j, count:

• left_less: elements before j that are smaller than rating[j]
• left_greater: elements before j that are larger than rating[j]
• right_less: elements after j that are smaller than rating[j]
• right_greater: elements after j that are larger than rating[j]

Increasing triplets through j = left_less * right_greater

Decreasing triplets through j = left_greater * right_less

Why does this work? For an increasing triplet (i, j, k), you need some element before j that is smaller (that is i) and some element after j that is larger (that is k). Each valid i can pair with each valid k independently, so you multiply the counts. The same logic applies in reverse for decreasing triplets.

The solution

def num_teams(rating: list[int]) -> int:
    n = len(rating)
    count = 0

    for j in range(n):
        left_less = 0
        left_greater = 0
        right_less = 0
        right_greater = 0

        for i in range(j):
            if rating[i] < rating[j]:
                left_less += 1
            elif rating[i] > rating[j]:
                left_greater += 1

        for k in range(j + 1, n):
            if rating[k] > rating[j]:
                right_greater += 1
            elif rating[k] < rating[j]:
                right_less += 1

        count += left_less * right_greater
        count += left_greater * right_less

    return count

For each middle index j, we scan everything to the left and count how many values are smaller versus larger than rating[j]. Then we scan everything to the right and do the same. The number of increasing triplets through j is left_less * right_greater, because any of the left_less elements can serve as the first element and any of the right_greater elements can serve as the third. We add left_greater * right_less for the decreasing triplets. Summing over all j gives the total count.

Visual walkthrough

Let's trace through rating = [2, 5, 3, 4, 1] step by step. For each middle element j, we count the left and right contributions and compute the number of valid triplets passing through that position.

Notice that j=0 and j=4 (the first and last elements) can never be the middle element of a triplet, so we only need to consider j=1, 2, 3. Each middle element contributes independently, and the grand total is the sum of all contributions.

Complexity analysis

Time is O(n^2). For each of the n positions j, we scan up to n elements to the left and n elements to the right. The total work is proportional to n^2. This is a large improvement over the O(n^3) brute force that checks every triplet directly.

Space is O(1). We only use a handful of integer variables (the four counters and the running total). No additional arrays or data structures are needed.

The building blocks

1. Fix the middle element

The core technique here is choosing one position to "anchor" and counting valid configurations around it. Instead of iterating over all triples (i, j, k), you iterate over j and ask: "how many valid i values exist on the left, and how many valid k values exist on the right?" This reduces a three-variable problem to a one-variable problem with two sub-scans.

for j in range(n):
    left_less = sum(1 for i in range(j) if rating[i] < rating[j])
    right_greater = sum(1 for k in range(j + 1, n) if rating[k] > rating[j])
    count += left_less * right_greater

2. Multiplication principle for independent choices

When two choices are independent (picking i from the left does not constrain which k you pick from the right), the total number of valid combinations is the product of the individual counts. This is the multiplication principle from combinatorics. You will see it in problems like 3Sum (after sorting), counting rectangles, and any problem where you decompose a multi-element selection into independent parts.

3. Symmetric counting for both directions

The same logic that counts increasing triplets also counts decreasing ones. You just swap which counts you multiply: left_greater * right_less instead of left_less * right_greater. Recognizing this symmetry means you only need to write the counting logic once and apply it twice with different variable pairings.

Edge cases

• All ratings in increasing order (e.g., [1, 2, 3, 4]): every triplet of indices (i, j, k) with i < j < k is valid as an increasing triplet. The count equals C(n, 3) = n*(n-1)*(n-2)/6. No decreasing triplets exist.
• All ratings in decreasing order (e.g., [4, 3, 2, 1]): symmetric to the above. Every triplet is a valid decreasing triplet. No increasing triplets exist.
• n = 3: there is exactly one triplet to check. The answer is 0, 1, or 2 depending on whether the three values are increasing, decreasing, or neither.
• n < 3: impossible to form any team. Return 0. (The constraints guarantee n is at least 1, so handle this as a guard clause.)
• Two equal ratings: the problem states all ratings are unique, so you do not need to handle ties. Every comparison is strict.

From understanding to recall

You have seen how fixing the middle element turns a triple-nested loop into a double loop with clean counting. The logic is a direct application of the multiplication principle: left choices times right choices. But reproducing it under pressure requires more than understanding.

The details that matter: scanning left for both "less" and "greater" counts, scanning right for both, and multiplying the correct pairs (left_less with right_greater for increasing, left_greater with right_less for decreasing). Mixing up the pairings gives the wrong answer. Forgetting to sum over all j gives a partial answer.

Spaced repetition makes these details automatic. You practice writing the middle-element loop, the four counters, and the two multiplication lines from scratch at increasing intervals. After a few rounds, you do not need to re-derive the pairing logic. You just write it.

Related posts

• Longest Increasing Subsequence - The classic dynamic programming problem for increasing subsequences, building on the same "compare elements in order" intuition
• Number of Longest Increasing Subsequence - Extends LIS to count the number of such subsequences, using similar multiplicative counting
• 132 Pattern - Another triplet-finding problem that rewards fixing one element and reasoning about what appears on either side

CodeBricks breaks Count Number of Teams into its middle-element fixing, left-right scanning, and multiplicative counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a triplet counting problem shows up in your interview, you do not hesitate. You just write it.