Longest Subsequence With Limited Sum - Video Solutions

Problem Overview: You get an integer array nums and multiple query values. For each query, return the maximum length of a subsequence whose total sum is less than or equal to that query. The subsequence can contain any elements from the array but must respect the sum constraint.

Approach 1: Greedy with Sorting and Prefix Sum (Time: O(n log n + n·q), Space: O(n))

The key observation: to maximize subsequence length under a sum limit, you should always pick the smallest numbers first. Sort the array using sorting. After sorting, compute a prefix sum array where prefix[i] represents the sum of the smallest i+1 numbers. For each query, iterate through the prefix array and find the largest index where the prefix sum is ≤ the query value. That index + 1 is the maximum subsequence length you can build.

This works because any larger number would increase the sum faster and reduce how many elements you can include. The greedy choice of always taking the smallest available numbers guarantees the longest valid subsequence. This approach is easy to implement but scanning the prefix array for every query leads to O(n) work per query.

Approach 2: Binary Search on Prefix Sums (Time: O(n log n + q log n), Space: O(n))

After sorting the array and building the prefix sums, the prefix array becomes monotonically increasing. That property allows you to apply binary search. For each query, perform a binary search on the prefix array to find the rightmost index where prefix[i] ≤ query. The position of that index determines the maximum number of elements you can include.

Binary search reduces each query from O(n) to O(log n). The preprocessing step (sorting and building prefix sums) still takes O(n log n), but query handling becomes much faster for large input sizes. This pattern—sort → prefix sum → binary search—is common in problems where you repeatedly check cumulative limits.

Recommended for interviews: Start by explaining the greedy idea: choosing the smallest numbers maximizes how many elements fit under the sum constraint. Build prefix sums to track cumulative totals. The optimal implementation uses binary search on the prefix array, achieving O(n log n + q log n). Mentioning the linear scan version first shows you understand the structure of the problem, while the binary search optimization demonstrates strong knowledge of array processing and query optimization.