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.This approach involves checking all possible combinations of three soldiers using nested loops to see if they can form a valid team. Although simple, this approach can be optimized by ensuring we scoot to the inner loops only when conditions are satisfied.
The brute force solution uses three nested loops to iterate over all possible triplets of indices (i, j, k) and checks if they form a valid team according to the given conditions.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3), where n is the length of the input array 'ratings'. This results from three nested loops each iterating over up to n elements.
Space Complexity: O(1), as it uses a constant amount of additional space.
This approach reduces the number of nested loops from three to two by counting the number of elements to the left and right that satisfy the increasing or decreasing condition required for forming a team.
This C solution optimizes the number of checks by reducing it to O(n^2). It calculates the number of elements on the left and right of each soldier which are lesser or greater. These counts are then used to compute the number of valid teams involving that soldier.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), where n is the length of the input array 'ratings'. This results from three nested loops each iterating over up to n elements. Space Complexity: O(1), as it uses a constant amount of additional space. |
| Optimized Counting Approach | Time Complexity: O(n^2) Space Complexity: O(1) |
Count Number of Teams - Leetcode 1395 - Python • NeetCodeIO • 14,668 views views
Watch 9 more video solutions →Practice Count Number of Teams with our built-in code editor and test cases.
Practice on FleetCode