C++ || 3 different approaches || segment tree, bf, two pointers || O(n log n) solution
Please let me know if you can think of another approach.\n# Approach 1 : Segment Tree\nThis is likely a bit of an overkill for this problem. Once we have the ma
Please let me know if you can think of another approach.\n# Approach 1 : Segment Tree\nThis is likely a bit of an overkill for this problem. Once we have the machinery for the segment tree in place solving the problem is easy we need to query how many elements we have seen so far that are smaller than the target minus the current number and then update the segment tree. If the input range is fixed this could also be used for a streaming problem, i.e. where you would only see one of the input elements at a time.\n\n```cpp\nclass SegmentTree {\nprivate:\n    const int n_;\n    vector<int> tree_;\n\n    constexpr static uint32_t next_pow2(uint32_t x) {\n        return x == 1 ? 1 : 1 << (32 - __builtin_clz(x-1));\n    }\n    \npublic:\n    SegmentTree(int n) : n_(next_pow2(n)), tree_(n_ * 2) {}\n    \n    void inc(int index) {\n        for (int i = (n_ + index); i >= 1; i /= 2) ++tree_[i];\n    }\n    \n    int query(int left, int right) const {\n        return query(1, 0, n_ - 1, left, right);\n    }\n    \nprivate:\n    int query(int node, int node_lo, int node_hi, int query_lo, int query_hi) const {\n        if (query_lo <= node_lo && node_hi <= query_hi) return tree_[node];\n        if (query_hi < node_lo || query_lo > node_hi) return 0;\n        const int last_in_left = (node_lo + node_hi) / 2;\n        return\n            query(node * 2, node_lo, last_in_left, query_lo, query_hi) +\n            query(node * 2 + 1, last_in_left + 1, node_hi, query_lo, query_hi);\n    }\n};\n\nclass Solution {\npublic:\n    static int countPairs(const vector<int>& nums, int target) {\n        const int offset = 64;\n        SegmentTree st(128);\n        int ans = 0;\n        for (int num : nums) {\n            ans += st.query(0, max(0, target - 1 - num + offset));\n            st.inc(num + offset);\n        }\n        return ans;\n    }\n};\n```\n\n**Complexity Analysis**\nLet $$n$$ be the length of the input vector and $$M$$ the size of the input range then the\n\n* Time complexity is $$O(n \\log M)$$ as we need to look at each input element and updating and querying the segment tree is $$O(\\log M)$$ and the \n\n* Space comlexity is $$O(\\log M)$$ for the segment tree.\n\n# Approach 2: nested loops\nThe obvious solution is just nested loops given the problem constraints doing someting $$O(n^2)$$ is totally ok.\n\n```cpp\n    static int countPairs(const vector<int>& nums, int target) {\n        int ans = 0;\n        for (int i = 0; i < size(nums); ++i)\n            for (int j = i + 1; j < size(nums); ++j)\n                ans += nums[i] + nums[j] < target;\n        return ans;\n    }\n```\n\n**Complexity Analysis**\nLet $$n$$ be the length of the input vector and $$M$$ the size of the input range then the\n\n* Time complexity is $$O(n^2)$$ as we need to traverse the input in a nested loop and the\n\n* Space comlexity is $$O(1)$$ as we only need loop variables.\n# Approach 3: sort and two pointers\nThis solution remindes me a bit of [1. Two Sum](https://leetcode.com/problems/two-sum/) or similar problems, and is inspired by [a post by @sensaurabh](https://leetcode.com/problems/count-pairs-whose-sum-is-less-than-target/discuss/3932143/two-pointers-solution). IMO this is the best approach to this problem.\n\n```cpp\n    static int countPairs(vector<int>& nums, int target) {\n        sort(begin(nums), end(nums));\n        int lo = 0;\n        int hi = size(nums) - 1;\n        int ans = 0;        \n        while (lo < hi) {\n            if (nums[lo] + nums[hi] < target) {\n                ans += hi - lo;\n                ++lo;\n            } else {\n                --hi;\n            }\n        }\n        return ans;\n    }\n```\n\n**Complexity Analysis**\nLet $$n$$ be the length of the input vector and $$M$$ the size of the input range then the\n\n* Time complexity is $$O(n \\log n)$$ for sorting the input, the traversal is $$O(n)$$ and the\n\n* Space comlexity is $$O(\\log n)$$ for ```std::sort()``` and the rest is only loop variables.\n\n_As always: Feedback, questions, and comments are welcome. Leaving an up-vote sparks joy! :)_\n\n**p.s. Join us on the [LeetCode The Hard Way Discord Server](https://discord.gg/hFUyVyWy2E)!**\n
['Tree', 'C']