Scale Engineer

Longest Subsequence With Limited Sum

Easy
#2174Time: 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).
Patterns
GreedyPrefix Sum
Algorithms
Binary SearchSorting
Data structures
Array

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

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).

Trade-offs

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.

Solutions

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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem