Longest Subsequence With Limited Sum

Updated on 05 June, 2025
Longest Subsequence With Limited Sum header image

Problem Statement

In this problem, we are given two integer arrays, nums and queries. The objective is to determine, for each query, the maximum size of a subsequence from nums such that the sum of the subsequence's elements is less than or equal to the query value. A subsequence, by definition, can be formed by removing some or none of the elements from an array without altering the order of the remaining elements. The output should be an array answer, where each answer[i] corresponds to the subsequence size for queries[i].

Examples

Example 1

Input:

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

Output:

[2,3,4]

Explanation:

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]

Explanation:

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

Approach and Intuition

To understand how to tackle this problem, let's break down the steps needed based on the insights gained from the examples and the constraints:

  1. Sort the Array: Begin by sorting nums in ascending order. This sorting assists in checking the smaller elements first, which are more likely to form valid subsequences under the sum constraints posed by queries.

  2. Initialize the Answer Array: An answer array of length m (same as queries) should be initialized to record the result for each query.

  3. Check Each Query with a Sorted nums:

    • For each query[i], initiate a sum variable to keep track of the running total of the subsequence and a count variable to count the number of elements included in this subsequence.
    • Traverse through the sorted nums and keep adding elements to the sum until adding another element would exceed the value of query[i].
    • Store the count in answer[i] which is the result for this particular query.
  4. Edge Considerations:

    • If nums contains only elements larger than the maximum query, the result will have answer[i] = 0 for some i because even the smallest element in nums is larger than the query.
    • All queries are addressed independently. Since arrays query and nums can have maximum lengths up to 1000, the described strategy should perform efficiently under the given constraints.

By sorting nums and independently checking each query, efficient determination of maximum subsequence size for each query is ensured, aligning with the requirements defined in the problem statement. This solution is effective due to its clarity and direct approach towards the problem's needs.

Solutions

  • C++
  • Java
  • Python
cpp
class Solution {
public:
    vector<int> processQueries(vector<int>& values, vector<int>& queries) {
        // Sorting values and computing prefix sums in place
        sort(values.begin(), values.end());
        for (int j = 1; j < values.size(); ++j)
            values[j] += values[j - 1];

        // Process each query to find how many elements have a sum less than or equal to query
        vector<int> results;
        for (auto q : queries) {
            int pos = upper_bound(values.begin(), values.end(), q) - values.begin();
            results.push_back(pos);
        }
        
        return results;
    }
};

The provided C++ solution is designed to determine the length of the longest subsequence from an array that fits within a sum limit as specified by multiple queries. Follow these steps to understand the approach:

  1. Sort the array values in non-decreasing order.
  2. Calculate the prefix sums of the sorted values array. This step updates each element in values such that each element at index j becomes the sum of all elements from the start up to j.
  3. Initialize an empty vector<int> named results to store the results of each query.
  4. For each query, use the upper_bound function to find the first position in the values where the prefix sum exceeds the query value. The upper_bound function returns an iterator pointing to the first element greater than the query value.
  5. Convert this iterator to an index using subtraction (upper_bound(values.begin(), values.end(), q) - values.begin()), and append this index to results. The index represents the number of elements up to (but not including) which the sum stays below or at the query value.
  6. Finally, the results vector containing the lengths of the longest subsequences for each query is returned.

This approach is efficient as it sorts the array and uses binary search (through upper_bound) to handle each query in logarithmic time relative to the size of the values array. The combination of sorting and prefix sum calculation allows for rapid queries, making the solution suitable for situations with multiple queries against a static or infrequently changed data set.

java
class Solution {
    public int[] processQueries(int[] elements, int[] queries) {
        // Sort elements and compute cumulative sums.
        Arrays.sort(elements);
        for (int i = 1; i < elements.length; i++)
            elements[i] += elements[i - 1];
        
        // Compare each query against the cumulative sum array.
        int queryCount = queries.length;
        int results[] = new int[queryCount];
        for (int q = 0; q < queryCount; q++) {
            int pos = locateInsertionPosition(elements, queries[q]);
            results[q] = pos;
        }
        
        return results;
    }
    
    int locateInsertionPosition(int[] array, int value) {
        int low = 0, high = array.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (array[mid] == value)
                return mid + 1;
            if (array[mid] < value)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return array[low] > value ? low : low + 1;
    }
}

The Java program you've provided solves the problem of finding the longest subsequence within a sorted array that has a cumulative sum less than or equal to the values specified in a series of queries. Here’s an overview of how your code accomplishes this:

  • First, it sorts the array of elements in ascending order. Post-sorting, it modifies this array into a prefix sum array where each element at index i stores the sum of elements from the start of the array up to index i.

  • The function processQueries is defined to handle multiple queries. Each query requires determining how many elements from the sorted, prefix-summed array can be summed without exceeding the query value. This determination is made for each value in the queries array.

  • For each query, the method locateInsertionPosition is invoked. This method performs a binary search to find the correct position in the prefix sum array where the cumulative sum stays below or exactly equal to the query value. The position indicates the number of elements in the original array that form a subsequence whose sum does not exceed the query value.

  • The binary search optimizes the process, making the function more efficient than a linear search approach. It adjusts the search bounds dynamically based on the mid-value comparison to the query value, fine-tuning the position where the cumulative sum just exceeds or meets the query value.

  • The results of all queries are stored in an array results, which is returned by processQueries. Each entry in results corresponds to the count of numbers in the initial array that sum up to less than or equal to the respective query in the queries array.

This method efficiently resolves the issue of finding subsequences under sum constraints through sorting, prefix sum calculation, and binary search.

python
class Solution:
    def solveQueries(self, numbers: List[int], requests: List[int]) -> List[int]:
        # Sort the numbers list
        numbers.sort()
        # Build prefix sum
        for i in range(1, len(numbers)):
            numbers[i] += numbers[i - 1]
        
        results = []
        
        # Process each query using binary search
        for request in requests:
            idx = bisect.bisect_right(numbers, request)
            results.append(idx)
        
        return results

The solution provided is designed to efficiently determine the longest subsequence length within an array that lies within a specified sum limit for a set of queries. The implementation uses Python 3 and involves sorting the input array and employing binary search through prefix sums for rapid query resolution. Here's a concise breakdown of the solution approach:

  • First, sort the input array of numbers to ensure binary search can be applied.
  • Compute the prefix sums of the array. This preprocesses the numbers such that each position i in the array numbers holds the sum of elements from the start up to i.
  • For each query in the list of requests, use bisect_right, a binary search technique from Python's bisect module, to find the insertion point that would maintain sorted order if the query value were inserted. The position returned by bisect_right effectively counts how many elements in the sorted prefix sums are less than or equal to the query value.
  • Append the index returned by bisect_right for each request to the results list, which effectively gives the length of the longest subsequence whose sum is within the respective request value.
  • Return the results list containing the lengths of the longest valid subsequences for each query in requests.

This approach ensures that the solution is both time-efficient, due to the logarithmic time complexity of binary search on a sorted list, and space-efficient as it only builds upon the existing array without requiring substantial additional storage.

Comments

No comments yet.