How hard is LeetCode 2902. Count of Sub-Multisets With Bounded Sum?

LeetCode 2902. Count of Sub-Multisets With Bounded Sum is rated Hard on LeetCode.

What is the time complexity of LeetCode 2902. Count of Sub-Multisets With Bounded Sum?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2902. Count of Sub-Multisets With Bounded Sum?

The Python solution on this page uses O(n) auxiliary space.

Count of Sub-Multisets With Bounded Sum — LeetCode 2902 Python Solution

HardArrayHash TableDynamic ProgrammingSliding Window

Problem: #2902
Pattern: Sliding Window
Reading time: 4 min
Source: leetcode.com

The problem

You are given a 0-indexed array nums of non-negative integers, and two integers l and r. Return the count of sub-multisets within nums where the sum of elements in each subset falls within the inclusive range of [l, r].

Example

Input: nums = [1,2,2,3], l = 6, r = 6
Output: 1
Explanation: The only subset of nums that has a sum of 6 is {1, 2, 3}.

Python solution

Python

class Solution:
    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:
        kMod = 1_000_000_007
        # dp[i] := # of submultisets of nums with sum i
        dp = [1] + [0] * r
        count = collections.Counter(nums)
        zeros = count.pop(0, 0)

        for num, freq in count.items():
            # stride[i] := dp[i] + dp[i - num] + dp[i - 2 * num] + ...
            stride = dp.copy()
            for i in range(num, r + 1):
                stride[i] += stride[i - num]
            for i in range(r, 0, -1):
                if i >= num * (freq + 1):
                    # dp[i] + dp[i - num] + dp[i - freq * num]
                    dp[i] = stride[i] - stride[i - num * (freq + 1)]
                else:
                    dp[i] = stride[i]

        return (zeros + 1) * sum(dp[l : r + 1]) % kMod

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 2902. Count of Sub-Multisets With Bounded Sum is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2902. Count of Sub-Multisets With Bounded Sum?: LeetCode 2902. Count of Sub-Multisets With Bounded Sum is rated Hard on LeetCode.
What is the time complexity of LeetCode 2902. Count of Sub-Multisets With Bounded Sum?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2902. Count of Sub-Multisets With Bounded Sum?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2902. Count of Sub-Multisets With Bounded Sum cover?: LeetCode 2902. Count of Sub-Multisets With Bounded Sum is tagged Array, Hash Table, Dynamic Programming and Sliding Window on LeetCode.