[Java] Two solutions explained
Bruteforce solution is straightforward. Just calculate all triplets.\nTime complexity is O(n ^ 3)\n\n\nclass Solution {\n    public int numTeams(int[] rating) {
Bruteforce solution is straightforward. Just calculate all triplets.\nTime complexity is O(n ^ 3)\n\n```\nclass Solution {\n    public int numTeams(int[] rating) {\n        int n = rating.length;\n        int answer = 0;\n        \n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                for (int g = j + 1; g < n; g++) {\n                    if (rating[i] < rating[j] && rating[j] < rating[g]\n                     || rating[i] > rating[j] && rating[j] > rating[g]) {\n                        answer++;\n                    }\n                }\n            }\n        }\n        \n        return answer;\n    }\n}\n```\n\nWe can eliminate one of loops with additional storage. For each index `i` calculate how many elements are bigger from left and how many elements are bigger from right. Store this computations in separate arrrays `numberOfBiggerFromLeft` and `numberOfBiggerFromRight`. Now, the answer is `sum(numberOfBiggerFromLeft[i] * numberOfSmallerFromRight[i] + numberOfSmallerFromLeft[i] * numberOfBiggerFromRight[i])` for each `0 < i < n` where `numberOfSmallerFromRight = n - i - 1 - numberOfBiggerFromRight[i]` and `numberOfSmallerFromLeft[i] = (i - numberOfBiggerFromLeft[i])`\n\n```\nclass Solution {\n    public int numTeams(int[] rating) {\n        int n = rating.length;\n        int answer = 0;\n        \n        int[] numberOfBiggerFromLeft = new int[n];\n        for (int i = 1; i < n; i++) {\n            for (int j = 0; j < i; j++) {\n                if (rating[j] > rating[i]) {\n                    numberOfBiggerFromLeft[i]++;\n                }\n            }\n        }\n        \n        int[] numberOfBiggerFromRight = new int[n];\n        for (int i = 0; i + 1 < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                if (rating[j] > rating[i]) {\n                    numberOfBiggerFromRight[i]++;\n                }\n            }\n        }\n        \n        for (int i = 0; i < n; i++) {\n            int rightToLeft = numberOfBiggerFromLeft[i] * (n - 1 - i - numberOfBiggerFromRight[i]);\n            int leftToRight = (i - numberOfBiggerFromLeft[i]) * numberOfBiggerFromRight[i];\n            answer += rightToLeft + leftToRight;\n        }\n        \n        return answer;\n    }\n}\n```
[]