Watch 10 video solutions for Count Number of Teams, a medium level problem involving Array, Dynamic Programming, Binary Indexed Tree. This walkthrough by NeetCodeIO has 14,668 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
i, j, k) with rating (rating[i], rating[j], rating[k]).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.length3 <= n <= 10001 <= rating[i] <= 105rating are unique.