Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1395.html
1395. Count Number of Teams
Level
Medium
Description
There are n
soldiers standing in a line. Each soldier is assigned a unique rating
value.
You have to form a team of 3 soldiers amongst them under the following rules:
- Choose 3 soldiers with index (
i
,j
,k
) with rating (rating[i]
,rating[j]
,rating[k]
). - A team is valid if: (
rating[i] < rating[j] < rating[k]
) or (rating[i] > rating[j] > rating[k]
) where (0 <= i < j < k < n
).
Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).
Example 1:
Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).
Example 2:
Input: rating = [2,1,3]
Output: 0
Explanation: We can’t form any team given the conditions.
Example 3:
Input: rating = [1,2,3,4]
Output: 4
Constraints:
n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5
Solution
The object of this problem is to find the number of monotone subsequences that have length 3 of the given array rating
. Since the length of rating
does not exceed 200, this problem can be solved by brute force. A solution of dynamic programming also exists.
Consider two cases, where each subsequence is monotonically increasing or monotonically decreasing. First consider the monotonically increasing case. Create an array dp
of length n
, wnere dp[i]
represents the number of elements in subarray rating[0..i - 1]
that are less than rating[i]
. Loop over i
from 1 to n - 1
. For each i
, loop over j
from i - 1
to 0. If rating[i] > rating[j]
, then increase dp[i]
by 1, and at the same time, if dp[j] > 0
, then there exist several elements before j
that are less than rating[j]
, so add dp[j]
to the number of teams. After the loop, the number of teams that are monotically increasing can be obtained.
For the monotonically decrease case, the logic is almost the same except that rating[i] < rating[j]
is used instead of rating[i] > rating[j]
.
Finally, return the number of teams of both cases.
-
class Solution { public int numTeams(int[] rating) { return numTeams(rating, true) + numTeams(rating, false); } public int numTeams(int[] rating, boolean increase) { int teams = 0; int length = rating.length; int[] dp = new int[length]; for (int i = 1; i < length; i++) { for (int j = i - 1; j >= 0; j--) { boolean flag = increase ? rating[i] > rating[j] : rating[i] < rating[j]; if (flag) { dp[i]++; if (dp[j] > 0) teams += dp[j]; } } } return teams; } }
-
class Solution: def numTeams(self, rating: List[int]) -> int: n, ans = len(rating), 0 for j in range(1, n - 1): ia = ib = ka = kb = 0 for i in range(j): if rating[i] < rating[j]: ia += 1 elif rating[i] > rating[j]: ib += 1 for k in range(j + 1, n): if rating[j] < rating[k]: ka += 1 elif rating[j] > rating[k]: kb += 1 ans += ia * ka + ib * kb return ans
-
class Solution { public: int numTeams(vector<int>& rating) { int n = rating.size(), ans = 0; for (int j = 1; j < n - 1; ++j) { int ia = 0, ib = 0, ka = 0, kb = 0; for (int i = 0; i < j; ++i) { if (rating[i] < rating[j]) ++ia; else if (rating[i] > rating[j]) ++ib; } for (int k = j + 1; k < n; ++k) { if (rating[j] < rating[k]) ++ka; else if (rating[j] > rating[k]) ++kb; } ans += ia * ka + ib * kb; } return ans; } };
-
func numTeams(rating []int) int { n, ans := len(rating), 0 for j := 1; j < n-1; j++ { ia, ib, ka, kb := 0, 0, 0, 0 for i := 0; i < j; i++ { if rating[i] < rating[j] { ia++ } else if rating[i] > rating[j] { ib++ } } for k := j + 1; k < n; k++ { if rating[j] < rating[k] { ka++ } else if rating[j] > rating[k] { kb++ } } ans += ia*ka + ib*kb } return ans }
-
class BinaryIndexedTree { private n: number; private c: number[]; constructor(n: number) { this.n = n; this.c = new Array(n + 1).fill(0); } public update(x: number, v: number): void { while (x <= this.n) { this.c[x] += v; x += x & -x; } } public query(x: number): number { let s = 0; while (x > 0) { s += this.c[x]; x -= x & -x; } return s; } } function numTeams(rating: number[]): number { let nums = [...rating]; nums.sort((a, b) => a - b); const n = rating.length; let m = 0; for (let i = 0; i < n; ++i) { if (i === 0 || nums[i] !== nums[i - 1]) { nums[m++] = nums[i]; } } nums = nums.slice(0, m); const search = (x: number): number => { let l = 0; let r = m; while (l < r) { const mid = (l + r) >> 1; if (nums[mid] >= x) { r = mid; } else { l = mid + 1; } } return l + 1; }; let ans = 0; const tree1 = new BinaryIndexedTree(m); const tree2 = new BinaryIndexedTree(m); for (const x of rating) { tree2.update(search(x), 1); } for (let i = 0; i < n; ++i) { const x = search(rating[i]); tree1.update(x, 1); tree2.update(x, -1); const l = tree1.query(x - 1); const r = n - i - 1 - tree2.query(x); ans += l * r; ans += (i - l) * (n - i - 1 - r); } return ans; }