Domain 2MediumMEDIUM

Count Number of Teams

Count valid teams of three soldiers with strictly increasing or decreasing ratings by iterating through each soldier as a potential middle member and counting smaller/larger neighbors.

Domain: medium•Updated: 2026-09-15
#counting#nested loops#O(n^2)#constant space

Problem Breakdown

We need to count the number of valid teams formed by three soldiers at indices i, j, and k where i < j < k. A team is valid if their ratings are strictly increasing (rating[i] < rating[j] < rating[k]) or strictly decreasing (rating[i] > rating[j] > rating[k]).

Inputs:

  • An array of unique integers representing soldier ratings.
  • Length nn (where 3 <= n <= 1000).

Outputs:

  • A single integer representing the total count of valid teams.

Implicit Constraints & Edge Cases:

  • Indices Order: The indices must be strictly increasing (i<j<ki < j < k). This means we are looking for subsequences, not just subsets.
  • Strict Inequality: Ratings cannot be equal within a team (handled naturally by < and > operators since all inputs are unique anyway).
  • Small Arrays: If n<3n < 3, the count is implicitly 0. The constraints guarantee n≥3n \ge 3.
  • Overflow: With N=1000N=1000, max teams ≈N3/6≈1.6×108\approx N^3/6 \approx 1.6 \times 10^8, which fits within a standard 32-bit integer, and definitely Python’s arbitrary precision integers.

Intuition

A brute-force solution would iterate through every possible triplet (i,j,k)(i, j, k) using three nested loops to check the condition. This results in O(n3)O(n^3) time complexity. For n=1000n=1000, this is roughly 10910^9 operations, which will likely exceed typical execution limits (usually ∼108\sim 10^8 ops/sec).

Key Insight: Instead of iterating over all triplets simultaneously, we can fix the middle element (jj) and count how many valid pairs exist to its left and right. Since i<j<ki < j < k, for a fixed middle index mid:

  1. We need soldiers on the left (0 to mid-1) that are smaller or larger than rating[mid].
  2. We need soldiers on the right (mid+1 to n-1) that satisfy the corresponding condition (larger if we want increasing, smaller for decreasing).

The number of valid teams centered at a specific soldier is simply: (count_left_smaller * count_right_larger) + (count_left_greater * count_right_smaller). This reduces the problem complexity to O(n2)O(n^2) because for each element (outer loop), we perform linear scans on its left and right neighbors.

Approach

  1. Initialize a variable total_teams to zero.
  2. Iterate through every index mid from 0 to n-1. This soldier acts as the middle member of potential teams.
  3. For each mid, initialize counters for:
    • Left elements smaller than current (left_smaller) and greater (left_greater).
    • Right elements larger than current (right_larger) and smaller (right_smaller).
  4. Iterate indices from 0 to mid-1 (Left) updating the left counters based on comparison with rating[mid].
  5. Iterate indices from mid+1 to n-1 (Right) updating the right counters similarly.
  6. Add (left_smaller * right_larger) and (left_greater * right_smaller) to total_teams.
  7. Return total_teams.

Complexity Analysis

Time Complexity: O(n2)O(n^2)

  • We iterate through each element once as the middle candidate (nn iterations).
  • For each iteration, we scan its left and right neighbors (up to nn operations combined).
  • Total operations are proportional to ∑i=1ni≈n2/2\sum_{i=1}^{n} i \approx n^2/2. With N=1000N=1000, this is roughly 500,000 operations, which fits comfortably within time limits.

Space Complexity: O(1)O(1)

  • We only use a few integer variables for counting and the input array itself (ignoring recursion stack or auxiliary structures). No additional data structures like hash maps are required.

Solution

from typing import List

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        total_teams = 0
        
        # Iterate through each soldier as the potential middle member of a team
        for mid in range(n):
            left_smaller = 0
            left_greater = 0
            
            right_larger = 0
            right_smaller = 0
            
            current_rating = rating[mid]
            
            # Count valid soldiers to the left (indices < mid)
            for i in range(mid):
                if rating[i] > current_rating:
                    left_greater += 1
                elif rating[i] < current_rating:
                    left_smaller += 1
            
            # Count valid soldiers to the right (indices > mid)
            for k in range(mid + 1, n):
                if rating[k] > current_rating:
                    right_larger += 1
                elif rating[k] < current_rating:
                    right_smaller += 1
            
            # Add combinations where left is smaller and right is larger (Increasing)
            total_teams += left_smaller * right_larger
            
            # Add combinations where left is greater and right is smaller (Decreasing)
            total_teams += left_greater * right_smaller
            
        return total_teams