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
- Fix the middle soldier
j. Any valid team is determined by choosing one soldier on each side. - Count
leftLess,leftGreater,rightLess,rightGreaterrelative torating[j]. - Increasing teams use
leftLess * rightGreater; decreasing teams useleftGreater * rightLess. - 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 isleftGreater * rightLess; swapping them overcounts. - Sorting the array: the index order
i < j < kis 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.