⚡Flashcard Drill➔
NeetCode #738LC-1395Medium2-D Dynamic Programming
← Back to All Problems

#738 · #1395 · Count Number of Teams(统计作战单位数)

📌 Problem Statement & Constraints

There are n soldiers with ratings rating[i]. A team of three indices i < j < k is valid if their ratings are strictly increasing or strictly decreasing. Return the number of valid teams. Constraints: 3 <= n <= 1000, 1 <= rating[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Fix the middle soldier j. Any valid team is determined by choosing one soldier on each side.
  2. Count leftLess, leftGreater, rightLess, rightGreater relative to rating[j].
  3. Increasing teams use leftLess * rightGreater; decreasing teams use leftGreater * rightLess.
  4. Summing these two products over every middle index gives the answer in O(n^2).

💻 Benchmark Python3 Implementation

class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n, teams = len(rating), 0
        for j in range(n):
            ll = lg = rl = rg = 0
            for i in range(j):
                if rating[i] < rating[j]:
                    ll += 1
                else:
                    lg += 1
            for k in range(j + 1, n):
                if rating[k] > rating[j]:
                    rg += 1
                else:
                    rl += 1
            teams += ll * rg + lg * rl
        return teams

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): each middle index scans the array once on each side.
💾 Space Complexity
O(1): four counters.

⚠️ Interview Pitfalls & Follow-ups

  • Triple nested loops: O(n^3) is about 10^9 operations for n = 1000; fixing the middle element reduces it to O(n^2).
  • Using non-strict comparisons: the problem requires strictly increasing or decreasing, so equal ratings must not form a team.
  • Mixing up the four counters: increasing is leftLess * rightGreater, decreasing is leftGreater * rightLess; swapping them overcounts.
  • Sorting the array: the index order i < j < k is intrinsic, so sorting destroys the structure.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems