Easy Explanation🔥Two Pointers | Cpp | Java | Python | Javascript🔥
Intuition\nThe main idea behind this approach is to use two pointers to form pairs of indices (left, right) such that the sum of the minimum and maximum element
# Intuition\nThe main idea behind this approach is to use two pointers to form pairs of indices (left, right) such that the sum of the minimum and maximum element in the subsequence formed by using the elements from nums[left] to nums[right] is less than or equal to the given target. To count all the subsequences that can be formed using the elements from nums[left+1] to nums[right], we can use the formula 2^(right-left), because for each element in this range, we can either choose to include it or exclude it from the subsequence, thus giving us 2 choices, and we have (right-left) such elements, hence the total number of subsequences that can be formed is 2^(right-left).\n\n# Approach\n- Sort the given array in non-decreasing order.\n- Traverse through the array using two pointers, one pointing to the left end and the other pointing to the right end.\n- For each pair of indices (left, right), if nums[left] + nums[right] <= target, then count all the subsequences of nums that can be formed using the elements from nums[left+1] to nums[right], and add it to the final result.\n- To count all the subsequences that can be formed using the elements from nums[left+1] to nums[right], we can use the formula 2^(right-left), because for each element in this range, we can either choose to include it or exclude it from the subsequence, thus giving us 2 choices, and we have (right-left) such elements, hence the total number of subsequences that can be formed is 2^(right-left).\n- Return the final result.\n\n# Complexity\n- Time complexity: O(nlogn), where n is the length of the given array. This is because we first sort the given array in non-decreasing order, which takes O(nlogn) time, and then we traverse through the array using two pointers, which takes O(n) time in the worst case.\n\n- Space complexity: O(1), since we only use a constant amount of extra space to store the two pointers and the final result.\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int numSubseq(vector<int>& nums, int target) {\n        const int mod = 1e9 + 7;\n        sort(nums.begin(), nums.end());\n        int left = 0, right = nums.size() - 1;\n        int result = 0;\n        while (left <= right) {\n            if (nums[left] + nums[right] <= target) {\n                result = (result + pow(2, right - left, mod)) % mod;\n                left++;\n            } else {\n                right--;\n            }\n        }\n        return result;\n    }\n};\n```\n```java []\nclass Solution {\n    public int numSubseq(int[] nums, int target) {\n        Arrays.sort(nums);\n        int n = nums.length;\n        int left = 0, right = n - 1;\n        int res = 0;\n        int mod = 1000000007;\n        while (left <= right) {\n            if (nums[left] + nums[right] <= target) {\n                res = (res + (int)Math.pow(2, right - left)) % mod;\n                left++;\n            } else {\n                right--;\n            }\n        }\n        return res;\n    }\n}\n\n```\n```python []\nclass Solution:\n    def numSubseq(self, nums: List[int], target: int) -> int:\n        nums.sort()\n        n = len(nums)\n        left, right = 0, n - 1\n        res = 0\n        mod = 10**9 + 7\n        while left <= right:\n            if nums[left] + nums[right] <= target:\n                res = (res + pow(2, right - left, mod)) % mod\n                left += 1\n            else:\n                right -= 1\n        return res\n\n```\n```javascript []\nvar numSubseq = function(nums, target) {\n    nums.sort((a, b) => a - b);\n    let n = nums.length;\n    let left = 0, right = n - 1;\n    let res = 0;\n    let mod = 1000000007;\n    while (left <= right) {\n        if (nums[left] + nums[right] <= target) {\n            res = (res + (2 ** (right - left)) % mod) % mod;\n            left++;\n        } else {\n            right--;\n        }\n    }\n    return res;\n};\n\n```\n**Please Upvote If You Found It Helpful**\n
['Two Pointers', 'C++', 'Java', 'Python3', 'JavaScript']