Problem Description

You have an integer array nums with length n and another integer array queries with length m.

For each query value queries[i], you need to find the maximum number of elements you can pick from nums such that their sum doesn't exceed queries[i]. The elements you pick must form a subsequence, meaning you can select any elements from nums but must maintain their original relative order.

Your task is to return an array answer of length m where answer[i] represents the maximum size of a valid subsequence for queries[i].

For example, if nums = [4, 5, 2, 1] and queries[i] = 3, you could pick elements [2, 1] (maintaining their order from the original array) with sum = 3, giving a subsequence size of 2. However, if you sort nums first to [1, 2, 4, 5], you could pick [1, 2] with the same sum but this represents the optimal greedy choice.

The solution works by:

1. Sorting nums in ascending order to greedily select smallest elements first
2. Creating a prefix sum array where s[i] represents the sum of the first i+1 smallest elements
3. For each query, using binary search to find the rightmost position in the prefix sum array where the sum is still ≤ queries[i], which gives the maximum number of elements that can be selected

Intuition

The key insight is that to maximize the number of elements in our subsequence while keeping the sum under a limit, we should greedily choose the smallest elements available. Think of it like filling a bag with a weight limit - you can fit more light items than heavy ones.

Since we want the maximum count of elements whose sum doesn't exceed a query value, we should always prefer smaller numbers. For instance, if we have [5, 2, 1, 4] and a limit of 6, choosing [1, 2] gives us 2 elements with sum 3, while choosing [5] only gives us 1 element with sum 5. Even though both are valid, we want the maximum count.

However, there's a constraint - we must maintain the relative order from the original array when forming subsequences. This might seem problematic at first, but here's the clever observation: since we're only counting the SIZE of the subsequence (not returning the actual subsequence), we can sort the array first! The sorted order doesn't violate the subsequence property because we're essentially asking "what's the maximum number of elements I can pick?" not "which specific elements should I pick in what order?"

Once sorted, the problem becomes straightforward: for each query, we want to include as many elements as possible starting from the smallest. This naturally leads to using prefix sums - prefix[i] tells us the sum of the first i+1 smallest elements. Then, for each query, we find the largest prefix sum that doesn't exceed the query value using binary search. The index where we stop tells us exactly how many elements we can include.

The bisect_right function finds the insertion point for the query value in the prefix sum array, which directly gives us the count of elements whose cumulative sum is ≤ the query value.

Learn more about Greedy, Binary Search, Prefix Sum and Sorting patterns.

Solution Approach

The implementation follows a three-step process using sorting, prefix sums, and binary search:

Step 1: Sort the array

nums.sort()

We sort nums in ascending order. This allows us to greedily select the smallest elements first. For example, if nums = [4, 5, 2, 1], after sorting we get [1, 2, 4, 5].

Step 2: Build prefix sum array

s = list(accumulate(nums))

The accumulate function creates a running sum array. If sorted nums = [1, 2, 4, 5], then s = [1, 3, 7, 12] where:

• s[0] = 1 (sum of first 1 element)
• s[1] = 1 + 2 = 3 (sum of first 2 elements)
• s[2] = 1 + 2 + 4 = 7 (sum of first 3 elements)
• s[3] = 1 + 2 + 4 + 5 = 12 (sum of all 4 elements)

Step 3: Binary search for each query

return [bisect_right(s, q) for q in queries]

For each query value q, we use bisect_right to find the insertion position in the prefix sum array. This position directly gives us the maximum number of elements we can select.

The bisect_right(s, q) function returns the rightmost position where we can insert q while maintaining sorted order. This position equals the count of elements in s that are ≤ q.

Example walkthrough:

• If s = [1, 3, 7, 12] and q = 5
• bisect_right(s, 5) returns 2
• This means we can take the first 2 elements (with sum = 3) but not the first 3 elements (with sum = 7)

Time Complexity: O(n log n + m log n) where n is the length of nums and m is the length of queries. Sorting takes O(n log n), building prefix sum takes O(n), and each of the m binary searches takes O(log n).

Space Complexity: O(n) for storing the prefix sum array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• nums = [4, 5, 2, 1]
• queries = [3, 10, 21]

Step 1: Sort the array First, we sort nums in ascending order:

• Original: [4, 5, 2, 1]
• Sorted: [1, 2, 4, 5]

Step 2: Build prefix sum array Next, we create a prefix sum array where each element represents the cumulative sum:

• s[0] = 1 (just the first element)
• s[1] = 1 + 2 = 3 (sum of first two elements)
• s[2] = 1 + 2 + 4 = 7 (sum of first three elements)
• s[3] = 1 + 2 + 4 + 5 = 12 (sum of all four elements)
• Prefix sum array: s = [1, 3, 7, 12]

Step 3: Process each query using binary search

For queries[0] = 3:

• We need to find how many elements from our sorted array can sum to at most 3
• Using bisect_right(s, 3) on [1, 3, 7, 12]
• The value 3 exists in the array at index 1, so bisect_right returns 2
• This means we can take 2 elements (the elements at indices 0 and 1 in sorted array: [1, 2] with sum = 3)
• answer[0] = 2

For queries[1] = 10:

• Using bisect_right(s, 10) on [1, 3, 7, 12]
• The value 10 would be inserted after 7 but before 12, at position 3
• This means we can take 3 elements (the elements at indices 0, 1, and 2: [1, 2, 4] with sum = 7)
• answer[1] = 3

For queries[2] = 21:

• Using bisect_right(s, 21) on [1, 3, 7, 12]
• The value 21 is larger than all values, so it would be inserted at the end, position 4
• This means we can take all 4 elements ([1, 2, 4, 5] with sum = 12)
• answer[2] = 4

Final Result: answer = [2, 3, 4]

The key insight is that by sorting first and using prefix sums, we can efficiently determine the maximum number of elements that fit within each query limit using binary search, all in logarithmic time per query.

Solution Implementation

Time and Space Complexity

Time Complexity: O((n + m) × log n)

• Sorting the nums array takes O(n log n) time, where n is the length of the nums array
• Creating the prefix sum array using accumulate takes O(n) time
• For each of the m queries, we perform a binary search using bisect_right on the sorted prefix sum array, which takes O(log n) time per query
• Total time for all queries: O(m × log n)
• Overall time complexity: O(n log n) + O(n) + O(m × log n) = O((n + m) × log n)

Space Complexity: O(n)

• The sorted nums array either modifies in-place or creates a new sorted array depending on Python's implementation, but we still need to store n elements
• The prefix sum array s stores n elements, requiring O(n) space
• The result list stores m elements, but this is typically not counted as auxiliary space since it's the output
• The sorting algorithm may use O(log n) space for the recursive call stack (if using quicksort or similar)
• Overall space complexity: O(n) for the prefix sum array, or O(log n) if only considering auxiliary space used by sorting

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding Subsequence vs Subarray Requirements

The Problem: A common mistake is thinking that we need to maintain the original order of elements when selecting them, which would make this problem significantly harder. Developers might attempt complex dynamic programming solutions to find valid subsequences while preserving original indices.

Why It Happens: The problem statement mentions "subsequence" and "maintaining relative order," which can be misinterpreted as needing to track original positions.

The Reality: Once we select which elements to include, we only need to maintain their relative order - but we're free to choose ANY elements from the array. This means sorting doesn't violate the subsequence property since we're just choosing the smallest elements available.

Solution: Recognize that sorting is valid because:

• We're selecting elements (not required to be consecutive)
• The "relative order" constraint only applies to the selected elements
• Greedy selection of smallest elements maximizes count

Pitfall 2: Integer Overflow with Large Arrays

The Problem: When dealing with large arrays or large element values, the prefix sum array might overflow, especially in languages with fixed integer sizes.

Example Scenario:

nums = [10**9] * 100000  # Very large values
# Prefix sum could exceed integer limits

Solution:

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
      
        # Build prefix sum with overflow check
        prefix_sums = []
        current_sum = 0
        for num in nums:
            current_sum += num
            # Early termination if sum exceeds max query value
            if queries and current_sum > max(queries):
                prefix_sums.append(current_sum)
                # Fill remaining with a large sentinel value
                prefix_sums.extend([float('inf')] * (len(nums) - len(prefix_sums)))
                break
            prefix_sums.append(current_sum)
      
        return [bisect_right(prefix_sums, query) for query in queries]

Pitfall 3: Inefficient Repeated Sorting

The Problem: If this function is called multiple times with the same nums array but different queries, sorting the array each time is wasteful.

Solution: Consider caching or preprocessing:

class SubsequenceSumSolver:
    def __init__(self, nums: List[int]):
        self.sorted_nums = sorted(nums)
        self.prefix_sums = list(accumulate(self.sorted_nums))
  
    def answer_query(self, query: int) -> int:
        return bisect_right(self.prefix_sums, query)
  
    def answer_queries(self, queries: List[int]) -> List[int]:
        return [self.answer_query(q) for q in queries]

Pitfall 4: Empty Array Edge Case

The Problem: Not handling the case where nums is empty or all elements exceed the query value.

Solution: The current implementation handles this correctly (bisect_right returns 0 for empty arrays), but it's worth being explicit:

def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
    if not nums:
        return [0] * len(queries)
  
    nums.sort()
    prefix_sums = list(accumulate(nums))
    return [bisect_right(prefix_sums, query) for query in queries]