#2389

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Longest Subsequence With Limited Sum

Find the maximum size of a subsequence from nums with a sum less than or equal to each query value.

array binary search greedy sorting prefix sum

Problem Statement

Given an integer array nums and an array of queries, return an array where each element represents the maximum size of a subsequence from nums such that the sum of its elements does not exceed the corresponding query value.

A subsequence is formed by deleting any elements from nums without changing the order of the remaining ones. The challenge is to compute the largest subsequence for each query in an optimal manner.

Examples

Example 1

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

Output: [2,3,4]

We answer the queries as follows:

The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.

Example 2

Input: nums = [2,3,4,5], queries = [1]

Output: [0]

The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.

Constraints

n == nums.length
m == queries.length
1 <= n, m <= 1000
1 <= nums[i], queries[i] <= 106

Solution Approach

Sorting and Prefix Sum

First, sort the nums array in ascending order. Then, compute the prefix sums of the sorted array. The prefix sum array allows us to quickly check how many elements we can sum up without exceeding the given query.

Binary Search

For each query, use binary search on the prefix sum array to find the largest subsequence whose sum is less than or equal to the query. This can be done in logarithmic time, speeding up the solution for large inputs.

Independent Query Evaluation

Each query can be processed independently, utilizing the same sorted prefix sum array. This reduces unnecessary recomputations and ensures that the solution scales efficiently with multiple queries.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this approach is dominated by the sorting step, which is O(n log n), and the binary search for each query, which is O(log n). Given m queries, the total time complexity is O(n log n + m log n). The space complexity is O(n) due to the prefix sum array.

What Interviewers Usually Probe

The candidate should demonstrate an understanding of binary search applied to a sorted array.
Look for the ability to break down the problem into subproblems like sorting and binary searching over a prefix sum.
The candidate should highlight solving each query independently to optimize the approach.

Common Pitfalls or Variants

Common pitfalls

Overlooking the importance of sorting the array before attempting to answer queries efficiently.
Incorrectly implementing binary search, leading to incorrect subsequences being selected for each query.
Neglecting the need to compute prefix sums, which is essential for optimizing the solution.

Follow-up variants

Adjust the problem to find subsequences with a sum strictly less than the query value.
Allow for multiple queries to be processed simultaneously using a more advanced algorithm like a segment tree.
Modify the problem to return the sum of the largest subsequence instead of its size.

FAQ

How do I apply binary search in the Longest Subsequence With Limited Sum problem?

Binary search is used to find the maximum subsequence size whose sum is less than or equal to each query value. You search for the largest sum in the sorted prefix sum array that satisfies the query condition.

What is the time complexity of solving the Longest Subsequence With Limited Sum problem?

The time complexity is O(n log n + m log n), where n is the length of the nums array and m is the number of queries. The dominant factor is O(n log n) due to sorting the nums array.

Can the prefix sum array be reused across multiple queries?

Yes, once the nums array is sorted and the prefix sum array is computed, it can be reused for all queries, ensuring that each query is answered in logarithmic time.

What if the nums array is unsorted? Should I sort it?

Yes, sorting the nums array is necessary to optimize the solution. The sorting step ensures that we can apply binary search efficiently and answer the queries in optimal time.

How does GhostInterview help with this problem?

GhostInterview assists by providing step-by-step guidance on applying binary search and prefix sums, helping you understand how to solve the problem efficiently for multiple queries.

terminal

Solution

Solution 1: Sorting + Prefix Sum + Binary Search

According to the problem description, for each $\textit{queries[i]}$, we need to find a subsequence such that the sum of its elements does not exceed $\textit{queries[i]}$ and the length of the subsequence is maximized. Obviously, we should choose the smallest possible elements to maximize the length of the subsequence.

1

2

3

4

5

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        s = list(accumulate(nums))
        return [bisect_right(s, q) for q in queries]

Solution 2: Sorting + Offline Query + Two Pointers

Similar to Solution 1, we can first sort the array $nums$ in ascending order.

1

2

3

4

5

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        s = list(accumulate(nums))
        return [bisect_right(s, q) for q in queries]

Continue Practicing

#2448 minimum cost to make array equal #2271 maximum white tiles covered by a carpet #2234 maximum total beauty of the gardens