Python 1498.py
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
result = 0
nums.sort()
for i in range(len(nums)):
a = nums[i]
b = target - a
if b < a:
break
other = bisect_right(nums, b)
between = other - i - 1
# each number between a and b can be there or not => like bits in a binary numbers
result += 2**between
result %= 10**9 + 7
return result
Difficulty
and has an acceptance rate of about 49% (500k+ submissions).
Typical patterns to solve this problem:
- Array
- Binary Search
- Sorting
- Two Pointers
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a class Solution with a method numSubseq that counts the number of non-empty subsequences of the input list nums whose minimum and maximum elements sum to a value not larger than target. The result is returned modulo (10^9+7). The algorithm first sorts the array, then iterates over possible minimum values, uses binary search to locate the farthest admissible maximum, and adds the combinatorial contribution of the elements that lie between them.
Key Steps
Sorting the input
nums.sort()
Sorting places the numbers in non-decreasing order, which enables the later binary search to work correctly and guarantees that once the current minimum exceeds the feasible maximum the loop can stop early.
Iterating over candidate minima
for i in range(len(nums)):
a = nums[i]
b = target - a
if b < a:
break
The loop walks through each element a as a potential smallest value of a subsequence. The complementary value b is the largest value allowed for the same subsequence because a + max ≤ target. The early termination condition b < a stops the iteration as soon as the smallest remaining element is already larger than the allowed maximum, ensuring that no further valid subsequences exist.
Locating the rightmost admissible maximum
other = bisect_right(nums, b)
bisect_right returns the index one past the last element that does not exceed b. Because the list is sorted, all elements with indices < other are ≤ b. This operation runs in logarithmic time and replaces a linear scan that would otherwise be required to find the boundary.
Computing the number of subsequences for the current window
between = other - i - 1
result += 2**between
result %= 10**9 + 7
between counts the elements that lie strictly between the chosen minimum a (at index i) and the farthest permissible maximum (at index other-1). Each of these interior elements may be either present or absent in a subsequence, giving 2**between distinct combinations. Adding this value to result accumulates the total count, and the modulo operation keeps the intermediate sum within the required range.
Edge Cases Handled
When the list contains duplicate values, sorting groups them together, and the binary search correctly includes all duplicates that satisfy the bound ≤ b. If target is smaller than twice the smallest element, the condition b < a becomes true on the first iteration, causing an immediate break and returning zero, which matches the expectation for an impossible target.
If target is large enough to accommodate the entire array, bisect_right will return len(nums), making between equal to the number of elements after the current minimum. The exponentiation 2**between then accounts for every possible selection of the remaining elements, correctly counting all subsequences that start with the current minimum.
When nums consists of a single element, the loop runs once, b equals target - a, and bisect_right yields either 1 (if a ≤ b) or 0. In the former case between becomes 0, and 2**0 adds one valid subsequence (the single-element subsequence). In the latter case the loop breaks without adding, yielding zero, which aligns with the definition that the subsequence must satisfy the sum constraint.
Performance Optimizations
The algorithm leverages sorting once at the beginning, which transforms the problem into a monotonic search space. By using bisect_right for each candidate minimum, it avoids scanning the tail of the array repeatedly; each binary search runs in logarithmic time, dramatically reducing the work compared with a naïve double loop.
The early break if b < a: break prevents unnecessary iterations once the smallest remaining element can no longer pair with any larger element to satisfy the target, cutting off the loop early in many cases.
Exponentiation 2**between is performed with Python’s built-in power operator, which uses fast exponentiation internally, ensuring that even large exponents are computed efficiently. The modulo operation is applied immediately after each addition, preventing the intermediate result from growing excessively large and keeping arithmetic operations fast.
Overall, the combination of sorting, binary search, early termination, and modular arithmetic yields a solution that scales well with input size while maintaining concise and readable code.
ELI5 - Simplified Explanation
Imagine you have a big treasure chest full of numbered blocks, and you want to pick some of them to follow a special rule. First, the code lines up all the blocks from the smallest number to the biggest number so they are nice and tidy. This makes it much easier to see which ones fit the rules.
The code looks at each block one by one, treating it as the smallest block in a new group. It then figures out how many other blocks are small enough to join that group without making a sum that is too big. Since some blocks are so tiny that they can either be included or left out, the code counts all the different ways those tiny blocks can be mixed and matched.
Every time it finds a new way to pick a group that works, it adds that to the total count. Because the number of ways can get giant, the code uses a little math trick to keep the total number from getting too big for the computer to handle. It just keeps counting until it has checked every possible group that follows the rule.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||
| WalkCCC | C++ | Java | Python | ||||||
| leetcode.ca | C++ | Java | Python | Go | Rust | TS | |||
| Progiez | C++ | Java | Python | ||||||
| github | black-shadows | C++ | |||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| FelixFan1122 | C# | ||||||||
| fsq | C++ | ||||||||
| JoshCrozier | JS | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| MacJim | C++ | ||||||||
| suxrobGM | C# | ||||||||
| varunu28 | Java | ||||||||
| vthwang | Java | ||||||||
| wisdompeak | C++ | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | ||||||||
| Progiez | C++, Java, Python | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| FelixFan1122 | C# | ||||||||
| fsq | C++ | ||||||||
| JoshCrozier | JavaScript | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| MacJim | C++ | ||||||||
| suxrobGM | C# | ||||||||
| varunu28 | Java | ||||||||
| vthwang | Java | ||||||||
| wisdompeak | C++ |
Videos
Similar Problems
- problem 3082: Find the Sum of the Power of All Subsequences
Solved On The Same Day
- problem 415: Add Strings
- problem 463: Island Perimeter
- problem 541: Reverse String II
- problem 1211: Queries Quality and Percentage
- problem 1251: Average Selling Price
- problem 1280: Students and Examinations
- problem 1327: List the Products Ordered in a Period
- problem 1378: Replace Employee ID With The Unique Identifier
- problem 1407: Top Travellers
- problem 1484: Group Sold Products By The Date
- problem 1517: Find Users With Valid E-Mails
- problem 1527: Patients With a Condition
- problem 1581: Customer Who Visited but Did Not Make Any Transactions
- problem 1587: Bank Account Summary II
- problem 1633: Percentage of Users Attended a Contest
- problem 1661: Average Time of Process per Machine
- problem 1667: Fix Names in a Table
- problem 1683: Invalid Tweets
- problem 1693: Daily Leads and Partners
- problem 1729: Find Followers Count
- problem 1731: The Number of Employees Which Report to Each Employee
- problem 1741: Find Total Time Spent by Each Employee
- problem 1757: Recyclable and Low Fat Products
- problem 1789: Primary Department for Each Employee
- problem 1795: Rearrange Products Table
- problem 1873: Calculate Special Bonus
- problem 1890: The Latest Login in 2020
- problem 1965: Employees With Missing Information
- problem 1978: Employees Whose Manager Left the Company
- problem 2356: Number of Unique Subjects Taught by Each Teacher
- problem 166: Fraction to Recurring Decimal
- problem 223: Rectangle Area
- problem 240: Search a 2D Matrix II
- problem 318: Maximum Product of Word Lengths
- problem 357: Count Numbers with Unique Digits
- problem 394: Decode String
- problem 1158: Market Analysis I
- problem 1341: Movie Rating
- problem 1492: The kth Factor of n
- problem 1907: Count Salary Categories
- problem 1934: Confirmation Rate
- problem 2405: Optimal Partition of String
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality