Count Number of Teams
MediumArrayDynamic ProgrammingBinary Indexed TreeSegment Tree
Solution
export function numTeams(rating: number[]): number {
const n = rating.length;
let answer = 0;
for (let mid = 1; mid < n - 1; mid++) {
let [leftGreater, leftLess] = [0, 0];
for (let left = 0; left < mid; left++) {
if (rating[left] > rating[mid]) {
leftGreater += 1;
} else {
leftLess += 1;
}
}
let [rightGreater, rightLess] = [0, 0];
for (let right = mid + 1; right < n; right++) {
if (rating[right] > rating[mid]) {
rightGreater += 1;
} else {
rightLess += 1;
}
}
answer += leftGreater * rightLess + leftLess * rightGreater;
}
return answer;
}
Complexity
- Time:
O(N^2)
- Space:
O(1)