[C++] Aggregator of solutions (O(n^2),O(nlogn)) with real load testing -> find out the best
People\'ve already published a lot of interesting solutions, I\'ve just gathered some of them, tuned the most optimal one, made a loading test and finally publi
People\'ve already published a lot of interesting solutions, I\'ve just gathered some of them, tuned the most optimal one, made a loading test and finally published the results. After each approach the complexity/space is specified. Copyright is respected, all sources are specified :)\n\nMy loading test is quite simple (I had to move ui32->ui64 to prevent overlow):\n```\n    using Solution=TSolutionOptimal; // change implementation here\n    constexpr size_t n=1e5; std::vector<int> v(n);\n    for(size_t i=0;i<n;++i) v[i]=i*117/71;\n    Solution s; DEBUG(s.numTeams(v));\n```\nRun as (debug/sanitize):\n```\n$ g++ --std=c++2a -Wall -Werror -g -fsanitize=address -march=native count-number-of-teams.cpp -o runner  && time ./runner\n```\nRun as (O3):\n```\n$ g++ --std=c++2a -Wall -Werror -O3 -march=native count-number-of-teams.cpp -o runner  && time ./runner\n```\n\nMy output in all cases:\n```\ns.numTeams(v) = 166661666700000\n```\nTimimgs:\n1. Brute force: O(n^2)/O(1):\nTime(Debug/sanitize)=1m19s, Time(O3)=0m0.980s\n2. Tree approach: O(n log n)/O(n):\nTime(Debug/sanitize)=1m31s, Time(O3)=0m36.928s\n3. Map+Fenwick: O(n log n)/O(n):\nTime(Debug/sanitize)=0m0.171s, Time(O3)=0m0.025s\n4. Sort+Fenwick: O(n log n)/O(n):\nTime(Debug/sanitize)=0m0.069s, Time(O3)=0m0.009s\n\n=== Details and code: ===\n\n1. Brute force: O(n^2)/O(1)\n```cpp\nclass TSolutionBruteForce {\n    using ui32=uint32_t;\n    using ui64=uint64_t;\npublic:\n    /* O(n^2) */\n    ui64 numTeams(const std::vector<int>& rating) {\n        const ui32 n=rating.size();\n        struct T{\n            ui32 Less=0;\n            ui32 Greater=0;\n        };\n        ui64 cnt=0;\n        for(ui32 mid=1;mid<n-1;++mid){\n            ui32 midL=mid; int currR=rating[mid]; T lcurr;\n            while(midL--){\n                lcurr.Less += rating[midL]<currR;\n                lcurr.Greater += rating[midL]>currR;\n            }\n            ui32 midR=mid; T rcurr;\n            while(++midR<n){\n                rcurr.Less += rating[midR]<currR;\n                rcurr.Greater += rating[midR]>currR;\n            }\n            cnt+=lcurr.Less*rcurr.Greater+lcurr.Greater*rcurr.Less;\n        }\n        return cnt;\n    }\n};\n```\nTime(Debug/sanitize)=1m19s, Time(O3)=0m0.980s\n\n2. Tree approach: O(n log n)/O(n) // actually copy-paste from votrubac post, details see in the original source: https://leetcode.com/problems/count-number-of-teams/discuss/554795/C%2B%2BJava-O(n--n)-and-O(n-log-n)\n```cpp\nclass TSolutionTree{\n    using ui32=uint32_t;\n    using ui64=uint64_t;\n    struct Tree {\n        Tree *left = nullptr, *right = nullptr;\n        int val = 0, cnt_left = 0;\n        Tree(int val) : val(val) {}\n    };\n    ui32 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    }\n    Tree* 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    }\n    Tree* 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    }\npublic:\n    /* O(n log n) */\n    ui64 numTeams(const std::vector<int>& rating) {\n        Tree left(rating.front()), right(rating.back());\n        ui64 res = 0; ui32 sz = rating.size();\n        for (ui32 i = 1; i < sz - 1; ++i)\n            insert(&right, rating[i]);\n        for (ui32 i = 1; i < sz - 1; ++i) {\n            remove(&right, rating[i]);\n            ui32 l_sm = count(&left, rating[i]), l_lg = i - l_sm;\n            ui32 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    }\n};\n```\nTime(Debug/sanitize)=1m31s, Time(O3)=0m36.928s (yeah, the solution leaks, no deletes in my version, probably fixed in the original post; I was interested in performance only and it\'s quite awful, so decided not to fix by myself, sorry)\n\n3. Map+Fenwick: O(n log n)/O(n). Copy-paste from: https://leetcode.com/problems/count-number-of-teams/discuss/555196/C%2B%2B-solutions-O(n-3)-O(n-2)-and-O(nlogn)\n```cpp\nclass TSolutionOptimalOriginal {\n    using ui32=uint32_t;\n    using ui64=uint64_t;\n    void update(std::vector<ui32> &v, ui32 i, const ui32 d) {\n        for (; i < v.size(); v[i] += d, i += (i & -i));\n    }\n\n    ui32 presum(const std::vector<ui32> &v, ui32 i) {\n        ui32 r = 0;\n        for (; i; r += v[i], i -= (i & -i));\n        return r;\n    }\n\npublic:\n    /* O(n log n) */\n    ui64 numTeams(const std::vector<int>& rating) {\n        std::map<int, ui32> have;\n        for (int x : rating) {\n            have[x];\n        }\n        ui32 n = 0;\n        std::vector<ui32> after(rating.size() + 1);\n        for (auto& t : have) {\n            update(after, t.second = ++n, 1);\n        }\n        std::vector<ui32> before(n + 1);\n        ui64 r = 0;\n        for (ui32 i = 0; i < n; ++i) {\n            const ui32 x = have[rating[i]], t1 = presum(before, x), t2 = presum(after, x);\n            r += t1 * (n - i - t2) + (i - t1) * (t2 - 1);\n            update(after, x, -1);\n            update(before, x, 1);\n        }\n        return r;\n    }\n};\n```\nTime(Debug/sanitize)=0m0.171s, Time(O3)=0m0.025s\n\n4. Sort+Fenwick: O(n log n)/O(n). Actually it\'s the tuned 3 version. std::map->std::sort+binary_search\n```cpp\nclass TSolutionOptimal {\n    using ui32=uint32_t;\n    using ui64=uint64_t;\n    void update(std::vector<ui32>& v, ui32 i, ui32 val){\n        while(i<v.size()){ v[i]+=val; i+=i&(-i); }\n    }\n    ui32 read(const std::vector<ui32>& v, ui32 i){\n        ui32 sum=0; while(i>0){ sum+=v[i]; i-=i&(-i); }\n        return sum;\n    }\n    ui32 find(const std::vector<int>& v, int val){\n        ui32 b=0,e=v.size()-1;\n        while(b<e){\n            ui32 mid=b+(e-b)/2;\n            if(v[mid]<val){\n                b=mid+1; continue;\n            }\n            if(v[mid]>val){\n                e=mid-1; continue;\n            }\n            return mid;\n        }\n        return b;\n    }\npublic:\n    /* O(n log n) */\n    ui64 numTeams(const std::vector<int>& rating) {\n        const ui32 n=rating.size();\n\n        std::vector<int> sorted(rating.begin(),rating.end());\n        std::sort(sorted.begin(),sorted.end());\n\n        std::vector<ui32> before(n+1),after(n+1);\n        for(ui32 x=1;x<=n;++x) update(after,x,1);\n\n        ui64 cnt=0;\n        for(ui32 i=0;i<n;++i){\n            int x=1+find(sorted,rating[i]), b=read(before,x), a=read(after,x);\n            cnt+=b*(n-i-a)+(i-b)*(a-1);\n            update(before,x,1); update(after,x,-1);\n        }\n        return cnt;\n    }\n};\n```\nTime(Debug/sanitize)=0m0.069s, Time(O3)=0m0.009s\n\nResume: cache-friendly approaches rule the world, the difference could be more than 2 times.
[]