Python Two pointers Complete Explanation
Show some love with upvotes if you found this helpful.Now,into the solution ===>\n\nSort the array, because subsequence is nothing but a subset.\n\nreason: A wi
Show some love with upvotes if you found this helpful.Now,into the solution ===>\n\nSort the array, because subsequence is nothing but a subset.\n\nreason: A window can be maintained [imin,j] such that\nif A[imin]+A[j]<=target\n    then,\n    for all i such that imin<=i<j\n        A[imin]+A[i] <= target is true.\n\n        \nThe idea is to find the imin for every j.\nThen,add all the possible subsequences that can be generated from this [imin,j] window.\n\nfor a window [imin,j], we can change the max by reducing j.\nBut,when imin changes the window shifts and the min+max<=target may not\nbe true anymore.\n\n```\nNo of subsequences for a window of [imin,j] are calculated as below:\n    Example:\n        sorted nums : [a,b,c,d]\n        lets say a+d<=target.\n        no of subsequences are:\n            1)when max reduces the min+max cant exceed target,so\n              [a,b,c,d], [a,b,c],[a,b],[a] => 3\n            2)[a,b,c,d] gives [a,b,d],[a,c,d],[a,d] with same min+max\n            3)[a,b,c] gives [a,c] with same min+max\n            4)[a,b] doesnt give anything new\n            5)[a] also remains same\n\n        The key thing to observe here is that, [a ,......] is the pattern\n        for every subsequence.\n        The no of subsets of the rest of the numbers\n        is the total no of subsequnces. i.e 1<<(numberofelements) or power(2,numberoflements)\n```\n\nTime : O(nlogn)\nSpace:O(1)\n\n```python\nclass Solution:\n    def numSubseq(self, nums: List[int], target: int) -> int:\n        nums.sort()\n        n = len(nums)\n        res = 0\n        #one length subsequence\n        mod = 10**9 + 7\n        i,j = 0,n-1\n        \n        \n        for i in range(n):\n            while i<=j and nums[i]+nums[j] > target:\n                j-=1\n            \n            if i<=j and nums[i] + nums[j] <= target:\n                res += pow(2,(j-i) , mod)\n                res %= mod\n        \n        return res\n```            \n
[]