1498. Number of Subsequences That Satisfy The Given Sum Condition - Explanation

Problem Link

Description

You are given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo (10^9) + 7.

Example 1:

Input: nums = [3,5,6,7], target = 9

Output: 4

Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10

Output: 6

Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Constraints:

  • 1 <= nums.length <= 100,000
  • 1 <= nums[i], target <= 1,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Brute Force (Recursion)

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 1000000007

        def dfs(maxi, mini, i):
            if i == len(nums):
                if mini != float("inf") and (maxi + mini) <= target:
                    return 1
                return 0

            skip = dfs(maxi, mini, i + 1)
            include = dfs(max(maxi, nums[i]), min(mini, nums[i]), i + 1)
            return (skip + include) % MOD

        return dfs(float("-inf"), float("inf"), 0)

Time & Space Complexity

  • Time complexity: O(2n)O(2 ^ n)
  • Space complexity: O(n)O(n) for recursion stack.
class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        MOD = 1000000007
        res = 0

        for i in range(len(nums)):
            if nums[i] * 2 > target:
                break

            l, r = i, len(nums) - 1
            while l <= r:
                mid = (l + r) // 2
                if nums[i] + nums[mid] <= target:
                    l = mid + 1
                else:
                    r = mid - 1

            count = pow(2, r - i, MOD)
            res = (res + count) % MOD

        return res

Time & Space Complexity

  • Time complexity: O(nlog⁡n)O(n \log n)
  • Space complexity: O(1)O(1) or O(n)O(n) depending on the sorting algorithm.

3. Two Pointers

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

        r = len(nums) - 1
        for i, left in enumerate(nums):
            while i <= r and left + nums[r] > target:
                r -= 1
            if i <= r:
                res += pow(2, r - i, mod)
                res %= mod

        return res

Time & Space Complexity

  • Time complexity: O(nlog⁡n)O(n \log n)
  • Space complexity: O(1)O(1) or O(n)O(n) depending on the sorting algorithm.

4. Two Pointers (Optimal)

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

        for i in range(1, len(nums)):
            power[i] = (power[i - 1] * 2) % MOD

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

        return res

Time & Space Complexity

  • Time complexity: O(nlog⁡n)O(n \log n)
  • Space complexity: O(n)O(n)