LC 1498: Two-pointer + Binary Search.

Find the problem description here. If you would like to read the solution in leetcode platform, find it here.

---

Intuition

All the two pointer approaches are good and enough. They move the left and the right pointers one by one. What I did was, I moved the left poniter using binary search to the last point where it still meets the condition with the current right pointer.

You can also move the right pointer as well in a similar fashion. I have pasted that code too here at the last fyr.

Approach

Take two pointers and keeping the condition nums[left] + nums[right] <= target, move the left and the right pointers.

Pre-computer the 2 powers.

After moving the left pointer to the point where it still satisfies the condition keeping the current right pointer, the sub-sequences formed will have a count something like this: Let us assume "l" is the last pointer from left where it still satisfies the condition with the current right pointer.

then, the count of sub-sequences will look something like this: $2^{right - left} + 2^{right - left + 1} + ... + 2^{right - l}$

let us assume, $(right - left) = n$. and $(right - l) = m$.
now, the above becomes:
$2^n + 2^{n + 1} + ... + 2^m$
$=> 2^n (1 + 2 + 2^2 + ... + 2^{m - n})$
$=> 2^n * (2^{m + 1} - 1)$

---

Complexity

• Time complexity: $O(n*logn)$ But, if we take $k$ steps one by one to move the left and the right pointer, here, it will only take $logk$ steps. Still, in worst case, it is the same.

• Space complexity: $O(n)$ to store the pre-computer 2 powers.

---

Code

Only moving the left pointer using binary search.

class Solution {
    long long MOD = 1e9 + 7;
public:
    int numSubseq(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        // pre-compute the 2 powers
        vector<long long> pwrs(n + 1, 1);
        for (int i = 1; i < n + 1; ++i) {
            pwrs[i] = pwrs[i - 1] * 2 % MOD;
        }
        
        long long result = 0;
        int left = 0, right = n - 1;
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                // binary search to find the range left
                // that satisfies the condition
                int l = left, r = right;
                while (l < r) {
                    int mid = l + (r - l + 1) / 2;  // upper mid
                    if (nums[mid] + nums[right] <= target) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }

                int p = right - l;
                int q = l - left;
                result = (result + (pwrs[p] * (pwrs[q + 1] - 1) % MOD)) % MOD;
            
                left = l + 1;
            }

            right--;
        }

        return (int) (result % MOD);
    }
};

---

Moving both the left and the right pointers using binary search.

class Solution {
    long long MOD = 1e9 + 7;
public:
    int numSubseq(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());

        // pre-compute the 2 powers
        vector<long long> pwrs(n + 1, 1);
        for (int i = 1; i < n + 1; ++i) {
            pwrs[i] = pwrs[i - 1] * 2 % MOD;
        }
        
        long long result = 0;
        int left = 0, right = n - 1;
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                // binary search to find the range left
                // that satisfies the condition
                int l = left, r = right;
                while (l < r) {
                    int mid = l + (r - l + 1) / 2;  // upper mid
                    if (nums[mid] + nums[right] <= target) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }

                int p = right - l;
                int q = l - left;
                result = (result + (pwrs[p] * (pwrs[q + 1] - 1) % MOD)) % MOD;
            
                left = l + 1;
            }

            // adjust the right as well with binary search
            if (left < right) {
                int l = left, r = right;
                while (l < r) {
                    int mid = l + (r - l + 1) / 2;
                    if (nums[left] + nums[mid] <= target) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }
                right = l;
            // this condition is to ensure we exit when left and right became equal.
            } else  right--;
        }

        return (int) (result % MOD);
    }
};

Hope it helps someone, thank you!