Solution
Approach 1
This is rather straightforward approach to solve the problem. For each element at index i, if we can find the number of elements smaller than the element on its left (index j < i), say leftSmall, and the number of elements larger on its right, say rightLarge (index k > i). Then, for case 1 where rating[i] < rating[j] < rating[k], the number of teams will be leftSmall*rightLarge. Similarly, for case 2, if we have leftLarge and rightSmall, number of teams is leftLarge*rightSmall.
int numTeams(vector<int>& rating) {
int res = 0;
for (auto i = 1; i < rating.size() - 1; ++i) {
int less[2] = {}, greater[2] = {};
for (auto j = 0; j < rating.size(); ++j) {
if (rating[i] < rating[j])
++less[j > i];
if (rating[i] > rating[j])
++greater[j > i];
}
res += less[0] * greater[1] + greater[0] * less[1];
}
return res;
}
Time complexity: O(n^2)
Space complexity: O(1)
Approach 2
Let us first focus only on the condition where rating[i] < rating[j] < rating[k]. For each index i, if we store the number of elements having rating less that rating[i] in an array lessThanArr then our task becomes simpler. Why? Suppose you are at an index j. Now, rating[j] will pair up with two integers, say h & i, where rating[h] < rating[i] < rating[j]. Now, if start iterating from j-1 to 0, then each index stores the number of elements having rating less than that. So for each such index i, it stores number of indices h. So j & i combined will make lessThanArr[i] triplets. Consider an example:
rating = [2,5,3,4,1]
lessThanArr = [0,1,1,2,0]
answer = 0 (initially)
Now, iterating from j = 1 to j = 4:
j=1
i=0 to i=0:
i=0: answer += lessThanArr[0] // note that lessThanArr[2] = 0 means that no number is less than 2 so it will always be the starting point of a triplet.
j=2
i=0 to i=1:
i=0: answer += lessThanArr[0] // series 2,3 so answer still = 0
i=1: 5 > 3 so no change
j=3
i=0 to i=2:
i=0: answer += lessThanArr[0] // series 2,4 so answer still = 0
i=1: 5 > 4 so no change
i=2: answer += lessThanArr[2] // answer now = 1. series 2,3,4
j=4
i=0 to i=3:
i=0: 2 > 1
i=1: 5 > 1
i=2: 3 > 1
i=3: 4 > 1
Final answer: 1
Note that we only considered the first case above where rating[i] < rating[j] < rating[k]. To consider the second case, we can simply reverse the input array and apply the same logic.
Code:
int numTeams(vector<int>& rating) {
vector<int> arr(rating.size(), 0);
int res = 0;
// case 1
for (int i=1; i<rating.size(); i++) {
int count = 0;
for (int j=0; j<i; j++) {
if (rating[j]<rating[i]) {
count++;
res += arr[j];
}
arr[i] = count;
}
}
for (int i=0; i<rating.size(); i++)
arr[i]=0;
// case 2
reverse(rating.begin(), rating.end());
for (int i=1; i<rating.size(); i++) {
int count = 0;
for (int j=0; j<i; j++) {
if (rating[j]<rating[i]) {
count++;
res += arr[j];
}
arr[i] = count;
}
}
return res;
}
Time complexity: O(n^2)
Space complexity: O(n)