Longest Subsequence With Limited Sum

Longest Subsequence With Limited Sum

What is this problem about?

The Longest Subsequence With Limited Sum problem gives you an integer array nums and an array of queries. For each query, you must find the maximum length of a subsequence from nums such that the sum of its elements is less than or equal to the query value. Because it is a subsequence, you can pick any elements from the array.

Why is this asked in interviews?

This is a highly popular entry-to-medium level question because it combines three fundamental concepts: Greedy choices, Prefix Sums, and Binary Search. It is the perfect problem for an interviewer to see if a candidate can optimize a multiple-query scenario. Brute-forcing each query takes $O(N \times Q)$, but properly combining these three concepts reduces it to an elegant $O(N \log N + Q \log N)$.

Algorithmic pattern used

1. Greedy & Sorting: Since we want the longest subsequence, we should greedily pick the smallest numbers. We start by sorting nums.
2. Prefix Sum: We transform the sorted array into a prefix sum array. Now, index i tells us the sum of the i+1 smallest elements.
3. Binary Search: For each query, we perform a binary search (like upper_bound or bisect_right) on the prefix sum array to find the largest index where the sum is $\le$ the query.

Example explanation

Let nums = [4, 5, 2, 1] and queries = [3, 10, 21].

1. Sort nums: [1, 2, 4, 5].
2. Create Prefix Sums: [1, 3, 7, 12]. (e.g., sum of 2 smallest is 3).
3. Answer queries:
   • Query 3: Find in [1, 3, 7, 12]. The value 3 is at index 1. Length is index + 1 = 2.
   • Query 10: Find in [1, 3, 7, 12]. The largest sum $\le 10$ is 7 (at index 2). Length is 3.
   • Query 21: The largest sum $\le 21$ is 12 (at index 3). Length is 4. The result is [2, 3, 4].

Common mistakes candidates make

A common mistake is forgetting that a "subsequence" allows you to pick elements from anywhere, which justifies the sorting step. If the problem asked for a "subarray" (contiguous), sorting would ruin the array's order. Another frequent error is manually iterating through the prefix sum array for each query instead of using Binary Search, which degrades performance when the number of queries is massive.

Interview preparation tip

To ace the Longest Subsequence With Limited Sum coding problem, master your language's built-in binary search tools for arrays (e.g., bisect_right in Python, Arrays.binarySearch in Java, upper_bound in C++). Knowing how to quickly find the insertion point of a number in a sorted prefix sum array is a superpower for tackling range-query interview questions efficiently.