# Longest Subsequence With Limited Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/longest-subsequence-with-limited-sum)
Canonical: https://scaleengineer.com/dsa/problems/longest-subsequence-with-limited-sum
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` of length `n`, and an integer array `queries` of length `m`.

Return _an array_ `answer` _of length_ `m` _where_ `answer[i]` _is the **maximum** size of a **subsequence** that you can take from_ `nums` _such that the **sum** of its elements is less than or equal to_ `queries[i]`.

A **subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

**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`

# Approaches
## Brute Force with Repeated Sorting
This approach iterates through each query and, for each one, sorts the `nums` array to greedily pick the smallest elements. This is highly inefficient because the sorting operation is repeated for every single query.
**Time:** O(m * n log n), where `n` is the number of elements in `nums` and `m` is the number of queries. For each of the `m` queries, we sort `nums` in O(n log n) time. · **Space:** O(n) to store a copy of the `nums` array for sorting. The space for the answer array is O(m).
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient due to repeated sorting, especially for a large number of queries.; Performs a lot of redundant work.
### Explanation
The core idea to maximize the subsequence size for a given sum is to always pick the smallest available numbers. This approach applies this greedy strategy directly for each query.

For every query `q` in `queries`:
1. A copy of the `nums` array is sorted in non-decreasing order.
2. We iterate through the sorted numbers, accumulating their sum and counting how many elements we've taken.
3. We stop when adding the next number would exceed the query limit `q`.
4. The final count for that query is stored.

This process is repeated for all queries, leading to a high time complexity due to the repeated sorting.

```java
import java.util.Arrays;

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        int m = queries.length;
        int[] answer = new int[m];

        for (int i = 0; i < m; i++) {
            int query = queries[i];
            int[] sortedNums = Arrays.copyOf(nums, nums.length);
            Arrays.sort(sortedNums);

            int count = 0;
            int currentSum = 0;
            for (int num : sortedNums) {
                if (currentSum + num <= query) {
                    currentSum += num;
                    count++;
                } else {
                    break;
                }
            }
            answer[i] = count;
        }
        return answer;
    }
}
```
### Algorithm
- Initialize an answer array `ans` of size `m`.
- For each query `queries[i]` from `i = 0` to `m-1`:
    - Create a copy of `nums` and sort it.
    - Initialize `count = 0` and `currentSum = 0`.
    - Iterate through the sorted `nums` array.
    - For each `num` in the sorted array:
        - If `currentSum + num <= queries[i]`, add `num` to `currentSum` and increment `count`.
        - Otherwise, break the loop.
    - Set `ans[i] = count`.
- Return `ans`.

## Optimized Iteration with Single Sort
This approach improves upon the brute-force method by recognizing that the `nums` array only needs to be sorted once. After an initial sort, we can iterate through the sorted array for each query to find the answer.
**Time:** O(n log n + m * n). Sorting takes O(n log n). Then, for each of the `m` queries, we iterate up to `n` times. · **Space:** O(log n) or O(n) for sorting, plus O(m) for the answer array. Typically stated as O(n) to include the answer array and potential sorting space.
**Pros:** Much more efficient than the first approach.; The logic remains straightforward.
**Cons:** Can still be slow if both `n` and `m` are large, as the complexity is dominated by the `m * n` term.
### Explanation
The key observation is that to maximize the subsequence length, we should always pick the smallest elements. The optimal order of elements to pick is always the same, regardless of the query sum limit.

Therefore, we can sort the `nums` array just one time at the beginning. After sorting, for each query `q`, we perform a linear scan through the sorted `nums` array. We add elements to our subsequence and keep a running sum. We stop when the sum exceeds `q`. The number of elements added is the answer for that query. This avoids the expensive O(n log n) sorting operation inside the query loop.

```java
import java.util.Arrays;

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int n = nums.length;
        int m = queries.length;
        int[] answer = new int[m];

        for (int i = 0; i < m; i++) {
            int query = queries[i];
            int count = 0;
            int currentSum = 0;
            for (int j = 0; j < n; j++) {
                if (currentSum + nums[j] <= query) {
                    currentSum += nums[j];
                    count++;
                } else {
                    break;
                }
            }
            answer[i] = count;
        }
        return answer;
    }
}
```
### Algorithm
- Sort the `nums` array in non-decreasing order.
- Initialize an answer array `ans` of size `m`.
- For each query `queries[i]` from `i = 0` to `m-1`:
    - Initialize `count = 0` and `currentSum = 0`.
    - Iterate through the now-sorted `nums` array.
    - For each `num` in `nums`:
        - If `currentSum + num <= queries[i]`, add `num` to `currentSum` and increment `count`.
        - Otherwise, break the loop.
    - Set `ans[i] = count`.
- Return `ans`.

## Prefix Sums with Binary Search
This is the most efficient approach. It involves pre-calculating the prefix sums of the sorted `nums` array. For each query, we can then use binary search on the prefix sum array to find the answer in logarithmic time.
**Time:** O(n log n + m log n). O(n log n) for sorting, O(n) for prefix sums, and O(m * log n) for `m` binary searches. · **Space:** O(log n) or O(n) for sorting. If modifying `nums` in-place, no extra space is needed for prefix sums. The answer array takes O(m). Overall, O(n) is a safe upper bound.
**Pros:** Highly efficient and optimal for the given constraints.; Scales well with a large number of queries.
**Cons:** Slightly more complex to implement due to the prefix sum calculation and binary search logic.
### Explanation
This method builds on the insight that we should always pick the smallest elements.

1.  First, sort the `nums` array.
2.  Next, compute the prefix sums of the sorted array. The `i`-th element of the prefix sum array will store the sum of the first `i+1` smallest numbers from `nums`. We can do this in-place to save space. Let `nums[i]` become `nums[0] + ... + nums[i]`.
3.  Now, for each query `q`, the problem is transformed into finding the maximum length `k` such that the sum of the `k` smallest elements is less than or equal to `q`. This is equivalent to finding the largest index `j` in the prefix sum array such that `prefix[j] <= q`. The answer for the query will then be `j + 1`.
4.  Since the prefix sum array is monotonically increasing, we can efficiently find this for each query using binary search.

```java
import java.util.Arrays;

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        // 1. Sort nums
        Arrays.sort(nums);
        int n = nums.length;
        int m = queries.length;

        // 2. Create prefix sums in-place
        for (int i = 1; i < n; i++) {
            nums[i] += nums[i - 1];
        }

        int[] answer = new int[m];
        // 3. For each query, binary search for the answer
        for (int i = 0; i < m; i++) {
            int query = queries[i];
            int count = binarySearch(nums, query);
            answer[i] = count;
        }

        return answer;
    }

    // This binary search finds the number of prefix sums less than or equal to target.
    private int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int ans = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                // This length (mid + 1) is a possible answer.
                // Try for a longer subsequence.
                ans = mid + 1;
                left = mid + 1;
            } else {
                // The sum is too large, try a shorter subsequence.
                right = mid - 1;
            }
        }
        return ans;
    }
}
```
### Algorithm
- Sort the `nums` array.
- Create a prefix sum array from the sorted `nums`. This can be done in-place.
- Initialize an answer array `ans` of size `m`.
- For each query `queries[i]`:
    - Perform a binary search on the prefix sum array to find the count of elements whose sum is less than or equal to `queries[i]`.
    - This is equivalent to finding the rightmost index `j` such that `prefix[j] <= queries[i]`. The answer is `j + 1`.
    - Store this count in `ans[i]`.
- Return `ans`.

# Solutions
### Python

```python
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]

```

### CSharp

```csharp
public class Solution {
    public int[] AnswerQueries(int[] nums, int[] queries) {
        int[] result = new int[queries.Length];
        Array.Sort(nums);
        for (int i = 0; i < queries.Length; i++) {
            result[i] = getSubsequent(nums, queries[i]);
        }
        return result;
    }
    public int getSubsequent(int[] nums, int query) {
        int sum = 0;
        for (int i = 0; i < nums.Length; i++) {
            sum += nums[i];
            if (sum > query) {
                return i;
            }
        }
        return nums.Length;
    }
}
```

### Java

```java
class Solution {
public
  int[] answerQueries(int[] nums, int[] queries) {
    Arrays.sort(nums);
    for (int i = 1; i < nums.length; ++i) {
      nums[i] += nums[i - 1];
    }
    int m = queries.length;
    int[] ans = new int[m];
    for (int i = 0; i < m; ++i) {
      ans[i] = search(nums, queries[i]);
    }
    return ans;
  }
private
  int search(int[] nums, int x) {
    int l = 0, r = nums.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] > x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number[]} queries * @return {number[]} */ var answerQueries =
  function (nums, queries) {
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) {
      nums[i] += nums[i - 1];
    }
    return queries.map((q) => _.sortedIndex(nums, q + 1));
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> answerQueries(vector<int> &nums, vector<int> &queries) {
    sort(nums.begin(), nums.end());
    for (int i = 1; i < nums.size(); i++) {
      nums[i] += nums[i - 1];
    }
    vector<int> ans;
    for (auto &q : queries) {
      ans.push_back(upper_bound(nums.begin(), nums.end(), q) - nums.begin());
    }
    return ans;
  }
};

```