LeetCode Entry
1395. Count Number of Teams
Count increasing or decreasing (i, j, k)
1395. Count Number of Teams medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/685
Problem TLDR
Count increasing or decreasing (i, j, k) #medium
Intuition
The brute-force n^3 solution is accepted.
Now, let’s think about the optimization. One way is to precompute some less[i] and bigger[i] arrays in O(n^2).
Another way is to just multiply count to the left and count to the right.
Approach
- just count the lesser values, the bigger will be all the others
- on the right side, just do the additions of the left counts
Complexity
-
Time complexity: \(O(n^2)\)
-
Space complexity: \(O(1)\)
Code
fun numTeams(rating: IntArray) =
rating.withIndex().sumOf { (i, r) ->
var s = (0..<i).count { rating[it] < r }
(i + 1..<rating.size).sumOf { if (rating[it] < r) i - s else s }
}
pub fn num_teams(rating: Vec<i32>) -> i32 {
(0..rating.len()).map(|i| {
let s = (0..i).filter(|&j| rating[j] < rating[i]).count();
(i + 1..rating.len()).map(|j|
if rating[j] < rating[i] { i - s } else { s } as i32
).sum::<i32>()
}).sum()
}