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.
1import java.util.*;
2
3public class Main {
4 public static int numTeams(int[] rating) {
5 int count = 0;
6 int n = rating.length;
7 for (int i = 0; i < n - 2; i++) {
8 for (int j = i + 1; j < n - 1; j++) {
9 for (int k = j + 1; k < n; k++) {
10 if ((rating[i] < rating[j] && rating[j] < rating[k]) ||
11 (rating[i] > rating[j] && rating[j] > rating[k])) {
12 count++;
13 }
14 }
15 }
16 }
17 return count;
18 }
19
20 public static void main(String[] args) {
21 int[] ratings = {2, 5, 3, 4, 1};
22 System.out.println(numTeams(ratings)); // Output: 3
23 }
24}This Java solution follows the same logic as the C/C++ implementations using nested loops to enumerate triplets.
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 <iostream>
2#include <vector>
using namespace std;
int numTeams(vector<int>& rating) {
int count = 0;
int n = rating.size();
for (int j = 0; j < n; j++) {
int less_left = 0, greater_left = 0, less_right = 0, greater_right = 0;
for (int i = 0; i < j; i++) {
if (rating[i] < rating[j]) less_left++;
else if (rating[i] > rating[j]) greater_left++;
}
for (int k = j + 1; k < n; k++) {
if (rating[j] < rating[k]) less_right++;
else if (rating[j] > rating[k]) greater_right++;
}
count += less_left * less_right + greater_left * greater_right;
}
return count;
}
int main() {
vector<int> ratings = {2, 5, 3, 4, 1};
cout << numTeams(ratings) << endl; // Output: 3
return 0;
}This C++ solution follows the same optimized strategy as the C solution, by reducing the problem complexity with judicious counting.