2389. Longest Subsequence With Limited Sum
Problem Description
The problem gives us two integer arrays: nums
which is of length n
, and queries
which is of length m
. Our task is to find, for each query, the maximum size of a subsequence that can be extracted from nums
such that the sum of its elements does not exceed the value given by the corresponding element in queries
.
It's important to recognize what a subsequence is. A subsequence is a new sequence generated from the original array where some (or no) elements are deleted, but the order of the remaining elements is retained. It's also worth noticing that there might be more than one subsequence that meets the condition for a query, and among those, we are looking to report the length of the largest one.
For example, suppose nums
= [4, 5, 2]
, and we have a single-element queries
= [6]
. The subsequences of nums
that have sums less than or equal to 6
are [4]
, [5]
, [2]
, and [4, 2]
. The longest of these is [4, 2]
, which has a length of 2
.
Intuition
To solve this problem, we first need to sort the nums
array. Sorting will help us easily find subsequences that maximize size while minimizing their sum—since we'll have guaranteed that we're always adding the smallest possible numbers (from the sorted array) to reach the sum required in the queries.
Next, we calculate the prefix sum of the nums
array after sorting it. This prefix sum array (s
) represents the sum of elements of nums
up to and including the i
th element. So the first element of the prefix sum will be equal to the first element of nums
, the second will be the sum of the first two elements of nums
, and so on.
Once we have the prefix sum array, we can easily determine, for each query, how many elements can be taken from the nums
array without exceeding the query sum. We do this by finding the rightmost index in the prefix sum array that is less than or equal to the query value. This index tells us the number of elements that can be included in the subsequence for a particular query.
The bisect_right
function from Python's bisect
module is a binary search function which returns the index where an element should be inserted to maintain the order. In our case, for each query, it finds the first element in the sorted prefix sum array s
that is greater than the query value—thus, the index we get is actually the length of the subsequence, because array indices are 0-based in Python.
Our final answer is an array of lengths, each corresponding to the maximum subsequence lengths that can be picked for each query without exceeding their sums.
The beauty of this approach is that by utilizing the sorted array and prefix sums, the time-consuming task of checking each possible subsequence is avoided, leading to a much more efficient solution.
Learn more about Greedy, Binary Search, Prefix Sum and Sorting patterns.
Solution Approach
The implementation of the solution can be broken down into the following steps:
-
Sort the Input Array: We start by sorting
nums
in ascending order. This arrangement guarantees that when we choose subsequences, we are choosing the smallest available elements first, which helps us maximize the number of elements in the subsequence for any given sum.1nums.sort()
-
Calculate Prefix Sums: We then compute a prefix sum array
s
from the sorted array. The prefix sum is a common technique used in algorithm design for quickly finding the sum of elements in a subarray. In Python, theaccumulate
function from theitertools
module can compute the prefix sums efficiently.1s = list(accumulate(nums))
-
Search with Binary Search: For each query, we use the
bisect_right
function to perform a binary search over the prefix sum array. This binary search will find the point where the query value (the sum we are not supposed to exceed) would be inserted to keep the arrays
sorted. Since arrays in Python are 0-indexed, the insertion index found bybisect_right
directly corresponds to the number of elements we can sum up from the sortednums
array to not exceed the query value. This is equivalent to the length of the required subsequence.1[bisect_right(s, q) for q in queries]
The implementation uses the following concepts:
-
Sorting: An essential part of this approach is to sort the
nums
array. Sorting helps us with a greedy-like approach to keep adding the smallest elements to reach the subsequence sum. -
Prefix Sums: The prefix sum array is constructed to have quick access to the sum of numbers from the start of the
nums
array up to any given point. -
Binary Search: The
bisect_right
function helps us to quickly find the rightmost location where a given query value would fit in the prefix sum array, which translates directly to the answer of how many elements can be used. -
Greedy Approach: The sorted array in combination with the prefix sums represents a greedy choice to choose the smallest elements to form subsequences.
The overall complexity of the algorithm is dominated by the sort operation, which is (O(n \log n)), where n
is the length of the nums
array. The prefix sum and binary searches for each query are (O(n)) and (O(\log n)) respectively, which are eclipsed by the sort operation when analyzing overall algorithm performance.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take small example arrays to walk through the solution approach described.
Suppose we have nums = [3, 7, 5, 6]
and queries = [7, 12, 5]
.
-
Sort the Input Array: We sort
nums
in ascending order.1nums.sort() # nums becomes [3, 5, 6, 7]
-
Calculate Prefix Sums: Next, we calculate the prefix sums of the sorted
nums
array.1s = list(accumulate(nums)) # s becomes [3, 8, 14, 21]
-
Search with Binary Search: We then perform binary searches on
s
by usingbisect_right
for each query.For the query value
7
:1bisect_right(s, 7) # returns 2 because '7' could be inserted at index 2 to keep 's' sorted
The subsequence
[3, 5]
sums up to8
, which is greater than7
. Thus, we only take the first element[3]
, resulting in a max subsequence length of1
.For the query value
12
:1bisect_right(s, 12) # returns 3 because '12' could be inserted at index 3 to keep 's' sorted
The subsequence
[3, 5, 6]
sums up to14
, exceeding12
. We exclude the last element and get[3, 5]
, resulting in a max subsequence length of2
.For the query value
5
:1bisect_right(s, 5) # returns 1 because '5' could be inserted at index 1 to keep 's' sorted
Here, only the first element
[3]
is less than or equal to5
, giving us a max subsequence length of1
.
The final answer for this example would be an array [1, 2, 1]
corresponding to the max subsequence lengths for each query.
Solution Implementation
1from bisect import bisect_right
2from itertools import accumulate
3
4class Solution:
5 def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
6 # Sort the array 'nums' to facilitate prefix sum calculation and binary search.
7 nums.sort()
8
9 # Calculate the prefix sums of the sorted array.
10 # 'prefix_sums' will hold the sum of numbers from start to the current index.
11 prefix_sums = list(accumulate(nums))
12
13 # Process each query and find out how many numbers in the sorted array
14 # have a sum less than or equal to the query number using binary search.
15 # This is done by finding the rightmost index to insert the query number
16 # in the prefix sum array such that it remains sorted.
17 # The result is stored in a list.
18 return [bisect_right(prefix_sums, query) for query in queries]
19
1class Solution {
2 public int[] answerQueries(int[] nums, int[] queries) {
3 // First, sort the array of nums.
4 Arrays.sort(nums);
5
6 // Create a prefix sum array using the sorted nums array.
7 for (int i = 1; i < nums.length; ++i) {
8 nums[i] += nums[i - 1];
9 }
10
11 // The length of the queries array.
12 int numQueries = queries.length;
13
14 // Initialize the answer array to store the results of each query.
15 int[] answers = new int[numQueries];
16
17 // Process each query using the search method.
18 for (int i = 0; i < numQueries; ++i) {
19 answers[i] = search(nums, queries[i]);
20 }
21 return answers;
22 }
23
24 // Perform a binary search to find the maximum length of a non-empty
25 // subsequence that is less than or equal to the query value.
26 private int search(int[] prefixSums, int targetValue) {
27 int left = 0, right = prefixSums.length;
28
29 // While the search space is valid
30 while (left < right) {
31 // Find the middle index of the current search space
32 int mid = (left + right) >> 1;
33
34 // If the subsequence sum at mid is greater than the target value,
35 // we need to look to the left half of the search space.
36 if (prefixSums[mid] > targetValue) {
37 right = mid;
38 } else {
39 // Otherwise, we look to the right half of the search space.
40 left = mid + 1;
41 }
42 }
43
44 // The binary search returns the maximum length of a non-empty
45 // subsequence whose sum is less than or equal to the target value.
46 return left;
47 }
48}
49
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Method to answer the queries based on the prefix sums of the sorted nums array
7 vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
8 // First, sort the input 'nums' array in non-decreasing order
9 sort(nums.begin(), nums.end());
10
11 // Create prefix sums in place
12 // After this loop, each element at index 'i' in 'nums' will represent the sum of all
13 // elements from index 0 to 'i'
14 for (int i = 1; i < nums.size(); i++) {
15 nums[i] += nums[i - 1];
16 }
17
18 // Initialize the vector to store the answers to the queries
19 vector<int> answers;
20
21 // Iterate through each query
22 for (const auto& query : queries) {
23 // 'upper_bound' returns an iterator pointing to the first element that is greater than 'query'
24 // Subtracting 'nums.begin()' from the iterator gives the number of elements that can be summed without exceeding 'query'
25 answers.push_back(upper_bound(nums.begin(), nums.end(), query) - nums.begin());
26 }
27
28 // Return the final answers for the queries
29 return answers;
30 }
31};
32
1/**
2 * Process and answer a set of queries based on prefix sums of a sorted array.
3 *
4 * @param nums The initial array of numbers.
5 * @param queries An array of query values.
6 * @returns An array of results, each representing the maximum length of
7 * a non-empty contiguous subarray that has a sum less than or
8 * equal to the query value.
9 */
10function answerQueries(nums: number[], queries: number[]): number[] {
11 // Sort the nums array in ascending order
12 nums.sort((a, b) => a - b);
13
14 // Calculate prefix sums in place, each element becomes the sum of all
15 // previous elements in the sorted array
16 for (let i = 1; i < nums.length; i++) {
17 nums[i] += nums[i - 1];
18 }
19
20 // Answer array to hold the maximum lengths per query
21 const answers: number[] = [];
22
23 // Binary search function to find out the maximum length of subarray
24 // for a single query
25 const binarySearch = (prefixSums: number[], target: number): number => {
26 let left = 0;
27 let right = prefixSums.length;
28
29 // Perform a binary search to find the right position where the sum
30 // exceeds the query value
31 while (left < right) {
32 const mid = Math.floor((left + right) / 2);
33 if (prefixSums[mid] > target) {
34 right = mid;
35 } else {
36 left = mid + 1;
37 }
38 }
39
40 // Return the index, which represents the maximum length of subarray
41 return left;
42 };
43
44 // Iterate through each query and use the binary search function
45 // to find the maximum length of subarray that fits the query condition
46 for (const query of queries) {
47 answers.push(binarySearch(nums, query));
48 }
49
50 // Return the final answers array with maximum lengths per query
51 return answers;
52}
53
Time and Space Complexity
The given code snippet defines a function answerQueries
which takes a list of numbers nums
and a list of queries queries
, then returns a list of integers. Let's analyze the time and space complexity of this function:
Time Complexity
nums.sort()
: Sorting thenums
list has a time complexity ofO(n log n)
, wheren
is the length ofnums
.list(accumulate(nums))
: Theaccumulate
function computes the prefix sums of the sortednums
list. Since it goes through each element once, it has a time complexity ofO(n)
.[bisect_right(s, q) for q in queries]
: For each queryq
inqueries
, thebisect_right
function performs a binary search on the lists
of prefix sums. Each binary search operation has a time complexity ofO(log n)
, and there arem
queries, so the overall time complexity for this step isO(m log n)
, wherem
is the length ofqueries
.
Combining these, the overall time complexity is O(n log n) + O(n) + O(m log n)
. Since O(n log n)
is the dominant term, the time complexity simplifies to O(n log n + m log n)
.
Space Complexity
- Sorting the list
nums
in-place doesn't require additional space, so its space complexity isO(1)
. - The list
s
of prefix sums would require additional space proportional to the length ofnums
. Hence, the space complexity for this step isO(n)
. - The list comprehension for bisect_right does not use additional space apart from the output list, which contains
m
elements. So, the space complexity for the output list isO(m)
.
Since O(n)
and O(m)
are not part of the same operation, we consider both for the overall space complexity. Thus, the overall space complexity of the function is O(n + m)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.