Problem 1498

Abstract / Summary

Count the number of subsequences where the sum of selected elements is within a given range.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
19 lines | 530 bytes | submitted September 7, 2023 | GitHub   7% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 49% (500k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Binary Search
  • Sorting
  • Two Pointers
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.74 | σ = 1.58

Complexity Analysis

Time: loglinear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
29 links | 17 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

30 easy 12 medium
43 solutions   September 7, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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