1498. Number of Subsequences That Satisfy the Given Sum Condition

I hate these array problem and subsequences… This is the daily challenge on 6 May 2023, I opened up the submission tab and found that I tried this problem 1 year ago and from the submission history, I recall how miserable it was…

Idea

I usually look for two ways to solve array+subsequence problem.

DP
Two pointers

This problem has a test case size of \(10^5\), so DP is out of the game, and two pointer does seem promising.

Another important thing to notice is that we only care about min and max value, and we’re working with subsequence. This means we no longer care the sequence of the give array, we can sort it!

Once the array is sorted, we can exploit it to apply two pointers.

The problem asks us to find subsequences that have min+max<=target, so we find the window which satisfy it and see what we can do.

eg:

array = [2,3,4,6,10,11] target = 12

Obviously we only care about [2,3,4,6,10], element 11 is never useful because even we pair it with the smallest element 2, the sum 11+2=13 is larger than target, so we can ignore it(and if we have more elements larger than that, ignore them all).

Next, what we do with the window(left=0, right=4)? Usually in such subsequence problem, we find “how many solutions are there that ends with a certain element”. However, in this case, it doesn’t make sense because we are finding min+max<=target, but this is a good start, we should think the opposite way, which is:

fix the left element, we can say that all combinations of [left+1,right] satisfy the condition. (find how many solutions are there that starts with a certain element)

This is because the max element in the window is the element at right, we are safe to pick it or any element that is smaller than it.

So at this step, we have \(2^{(right-left)}\) solutions.

Naturally, we want to know how many solutions we have if we move left to the next element, but we need to make sure the new elements on left and right doesn’t have a sum that exceeds target, if so, we move right-=1 until the sum is <= target.

We do this until the two pointers cross each other (pretty standard way to end two pointers solution).

Algorithm

Implementation based on the above idea.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


MOD=10**9+7
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l,r=0,len(nums)-1
        res=0

        while l<=r:
            if nums[l]+nums[r]>target:
                r-=1
            else:
                res+=2**(r-l)%MOD
                l+=1
        return res%MOD

There are two really boring optimizations that I don’t believe to be useful in an interview setting, but they do improve the runtime a lot.

use python’s pow(base,power,mod) function instead of manually mod each time we update res
cache the pow() result because the power is limited to the window length

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


MOD=10**9+7
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        l,r=0,len(nums)-1
        res=0

        @cache 
        def mypow(p):
            return pow(2,p,MOD)

        while l<=r:
            if nums[l]+nums[r]>target:
                r-=1
            else:
                res+=(mypow(r-l))
                l+=1
        return res%MOD

Idea#

Algorithm#

Idea

Algorithm