Sponsored
Sponsored
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.
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.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int numTeams(vector<int>& rating) {
6 int count = 0;
7 int n = rating.size();
8 for (int i = 0; i < n - 2; ++i) {
9 for (int j = i + 1; j < n - 1; ++j) {
10 for (int k = j + 1; k < n; ++k) {
11 if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
12 (rating[i] > rating[j] && rating[j] > rating[k])) {
13 count++;
14 }
15 }
16 }
17 }
18 return count;
19}
20
21int main() {
22 vector<int> ratings = {2, 5, 3, 4, 1};
23 cout << numTeams(ratings) << endl; // Output: 3
24 return 0;
25}Similar to the C approach, this C++ solution iterates over all possible triplets and checks if they form a valid team using nested loops.
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.
Time Complexity: O(n^2)
Space Complexity: O(1)
1#include
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.