Longest Subsequence With Limited Sum

Difficulty: Easy | Acceptance: 73.60% | Paid: No Topics: Array, Binary Search, Greedy, Sorting, Prefix Sum

You are given an integer array nums and an integer array queries of the same length.

For each queries[i], determine the maximum length of a subsequence of nums that satisfies the following conditions:

The sum of the chosen elements is less than or equal to queries[i]. The chosen elements are a subsequence of nums (i.e., they can be obtained by deleting some or no elements from nums without changing the order of the remaining elements).

Return an array answer of length queries.length where answer[i] is the answer to the ith query.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements.

• Examples
• Constraints
• Brute Force with Sorting
• Sorting + Prefix Sum + Binary Search
• Sorting + Prefix Sum + Two Pointers

Examples

Example 1:

Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation: 
- For the query 3, we can pick the subsequence [2,1] which has a sum of 3. The length is 2.
- For the query 10, we can pick the subsequence [4,5,1] which has a sum of 10. The length is 3.
- For the query 21, we can pick the subsequence [4,5,2,1] which has a sum of 12. The length is 4.

Example 2:

Input: nums = [2,3,4,5], queries = [1]
Output: [0]
Explanation: No subsequence can have a sum less than or equal to 1, so the answer is 0.

Constraints

n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 10^6

Brute Force with Sorting

Intuition To maximize the length of the subsequence for a limited sum, we should greedily pick the smallest numbers available. By sorting the array, we can simply iterate and accumulate elements until the sum exceeds the query.

Steps

• Sort the nums array in ascending order.
• Iterate through each query in queries.
• For each query, iterate through the sorted nums, accumulating the sum.
• Count how many elements can be taken before the sum exceeds the query.
• Store the count in the result array.

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        ans = []
        for q in queries:
            total = 0
            count = 0
            for num in nums:
                if total + num <= q:
                    total += num
                    count += 1
                else:
                    break
            ans.append(count)
        return ans

Complexity

• Time: O(N * Q + N log N), where N is the length of nums and Q is the length of queries. Sorting takes O(N log N), and the nested loops take O(N * Q).
• Space: O(1) or O(N) depending on the sorting algorithm.
• Notes: Simple to implement, but inefficient if both N and Q are large.

Sorting + Prefix Sum + Binary Search

Intuition After sorting, the sum of the first k elements is the smallest possible sum for any subsequence of length k. We can precompute prefix sums. Then, for each query, we perform a binary search on the prefix sum array to find the largest index where the sum is less than or equal to the query.

Steps

• Sort the nums array.
• Compute the prefix sum array prefix where prefix[i] is the sum of the first i elements of nums.
• For each query q, perform a binary search on prefix to find the rightmost index i such that prefix[i] <= q.
• The index i represents the maximum length of the subsequence.

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        prefix = [0]
        for num in nums:
            prefix.append(prefix[-1] + num)
        
        ans = []
        for q in queries:
            # bisect_right returns the insertion point to the right of any existing entries
            count = bisect_right(prefix, q)
            ans.append(count)
        return ans

Complexity

• Time: O(N log N + Q log N), where N is the length of nums and Q is the length of queries. Sorting takes O(N log N), and each query is answered in O(log N).
• Space: O(N) for the prefix sum array.
• Notes: This is the most efficient standard approach for this problem.

Sorting + Prefix Sum + Two Pointers

Intuition If we sort the queries as well, we can process them in increasing order. We maintain a pointer in the sorted nums array, accumulating the sum. As we move through the sorted queries, we advance the pointer in nums as long as the sum allows. This avoids binary search and processes queries in linear time relative to the number of elements.

Steps

• Sort nums.
• Create a list of pairs (query, original_index) for queries and sort this list based on the query value.
• Initialize a result array ans.
• Iterate through the sorted queries with a pointer i starting at 0 for nums.
• Maintain a running total.
• For each query, move the pointer i forward while total + nums[i] <= query.
• The answer for the current query is i.
• Place the answer in the correct position using the original_index.

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        # Create list of (value, index)
        sorted_queries = sorted([(q, i) for i, q in enumerate(queries)])
        
        ans = [0] * len(queries)
        total = 0
        count = 0
        
        for q, idx in sorted_queries:
            while count < len(nums) and total + nums[count] <= q:
                total += nums[count]
                count += 1
            ans[idx] = count
            
        return ans

Complexity

• Time: O(N log N + Q log Q), where N is the length of nums and Q is the length of queries. Sorting dominates the complexity.
• Space: O(Q) to store the sorted queries with indices.
• Notes: This approach is useful when Q is very large, as it avoids the log factor of binary search per query, though it requires sorting the queries.