C++/Java O(n * n) and O(n log n)
For each soldier, count how many soldiers on the left and right have less and greater ratings.\n\nThis soldier can form less[left] * greater[right] + greater[le
For each soldier, count how many soldiers on the left and right have `less` and `greater` ratings.\n\nThis soldier can form `less[left] * greater[right] + greater[left] * less[right]` teams.\n\n**Complexity Considerations**\n\nThe straightforward approach to count soldiers yields a quadratic solution. You might be tempted to use a set or something to count soldiers in O(log n) time.\n\nYou can find a rating in a set in O(log n), however, counting smaller (or larger) elements will still be linear. Unless you implement BST where each node tracks count of left children, a set approach will be quadratic as well.\n\n> Update: see approach 2 below for a simple linearithmic solution below.\n \n #### Approach 1: Count Left and Right\n**C++**\n```cpp\nint numTeams(vector<int>& rating) {\n    int res = 0;\n    for (auto i = 1; i < rating.size() - 1; ++i) {\n        int less[2] = {}, greater[2] = {};\n        for (auto j = 0; j < rating.size(); ++j) {\n            if (rating[i] < rating[j])\n                ++less[j > i];\n            if (rating[i] > rating[j])\n                ++greater[j > i];\n        }\n        res += less[0] * greater[1] + greater[0] * less[1];\n    }\n    return res;\n}\n```\n**Java**\n```java\npublic int numTeams(int[] rating) {\n    int res = 0;\n    for (int i = 1; i < rating.length - 1; ++i) {\n        int less[] = new int[2], greater[] = new int[2];\n        for (int j = 0; j < rating.length; ++j) {\n            if (rating[i] < rating[j])\n                ++less[j > i ? 1 : 0];\n            if (rating[i] > rating[j])\n                ++greater[j > i ? 1 : 0];\n        }\n        res += less[0] * greater[1] + greater[0] * less[1];\n    }\n    return res;\n}\n```\n**Complexity Analysis**\n- Time: O(n * n) \n- Memory: O(1)\n\n#### Approach 2: Sort Left and Right\nWe can store ratings on the left and right in the sorted order. As we process soldiers left-to-right, we move their rating from the right bucket to the left bucket.\n\nWe can use BST to store sorted ratings, and insert/remove ratings in O(log n). However, standard containers like `set` or `map` won\'t tell us how many elements are smaller than the given rating. You can locate a rating in O(log n), but counting elements smaller or larger will still br linear.\n\nTherefore, we need to implement our own BST that can tell us how many elements are less than a given rating in O(log n). For that, we will track the number of left children for each node, and accumulate it as we search in the tree. See `count` function below for more details.\n\n**Additional Considerations**\nWe need to balance BST in order to achieve O(n log n) time complexity in the worst case. Also, the simple implementation below does not handle duplicates.\n\n**C++**\n```cpp\nstruct Tree {\n    Tree *left = nullptr, *right = nullptr;\n    int val = 0, cnt_left = 0;\n    Tree(int val) : val(val) {}\n};\nint numTeams(vector<int>& rating) {\n    Tree left(rating.front()), right(rating.back());\n    int res = 0, sz = rating.size();\n    for (auto i = 1; i < sz - 1; ++i)\n        insert(&right, rating[i]);\n    for (auto i = 1; i < sz - 1; ++i) {\n        remove(&right, rating[i]);\n        int l_sm = count(&left, rating[i]), l_lg = i - l_sm;\n        int r_sm = count(&right, rating[i]), r_lg = (sz - 1 - i - r_sm) ;\n        res += l_sm * r_lg + l_lg * r_sm;\n        insert(&left, rating[i]);\n    }\n    return res;\n}\nint count(Tree* root, int val) {\n    if (root == nullptr)\n        return 0;\n    if (val < root->val)\n        return count(root->left, val);\n    return 1 + root->cnt_left + count(root->right, val);\n}\nTree* insert(Tree* root, int val) {\n    if (root == nullptr)\n        return new Tree(val);\n    if (val < root->val) {\n        ++root->cnt_left;\n        root->left = insert(root->left, val);\n    }\n    else\n        root->right = insert(root->right, val);\n    return root;\n}\nTree* remove(Tree* root, int val) {\n    if (root == nullptr)\n        return nullptr;\n    if (root->val == val) {\n        if (root->left == nullptr)\n            return root->right;\n        auto rightmost = root->left;\n        while (rightmost->right != nullptr)\n            rightmost = rightmost->right;\n        rightmost->right = root->right;\n        return root->left;\n    }\n    if (val < root->val) {\n        --root->cnt_left;\n        root->left = remove(root->left, val);\n    }\n    else\n        root->right = remove(root->right, val);\n    return root;\n}\n```\n**Complexity Analysis**\n- Time: O(n log n) in the average case. We need to implement tree balancing to achieve O(n log n) in the worst case. \n- Memory: O(n) for the trees.
[]