2389. Longest Subsequence With Limited Sum LeetCode Solution

In this guide, you will get 2389. Longest Subsequence With Limited Sum LeetCode Solution with the best time and space complexity. The solution to Longest Subsequence With Limited Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Longest Subsequence With Limited Sum solution in C++
Longest Subsequence With Limited Sum solution in Java
Longest Subsequence With Limited Sum solution in Python
Additional Resources

2389. Longest Subsequence With Limited Sum LeetCode Solution image

Problem Statement of Longest Subsequence With Limited Sum

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

Complexity Analysis

Time Complexity: O(\texttt{sort}(\texttt{nums}) + qn)
Space Complexity: O(q)

2389. Longest Subsequence With Limited Sum LeetCode Solution in C++

class Solution {
 public:
  vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
    vector<int> ans;

    ranges::sort(nums);

    for (const int query : queries)
      ans.push_back(numOfElementsLessThan(nums, query));

    return ans;
  }

 private:
  int numOfElementsLessThan(const vector<int>& nums, int query) {
    int sum = 0;
    for (int i = 0; i < nums.size(); ++i) {
      sum += nums[i];
      if (sum > query)
        return i;
    }
    return nums.size();
  }
};
/* code provided by PROGIEZ */

2389. Longest Subsequence With Limited Sum LeetCode Solution in Java

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

    Arrays.sort(nums);

    for (int i = 0; i < queries.length; ++i)
      ans[i] = numOfElementsLessThan(nums, queries[i]);

    return ans;
  }

  private int numOfElementsLessThan(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;
  }
}
// code provided by PROGIEZ

2389. Longest Subsequence With Limited Sum LeetCode Solution in Python

class Solution:
  def answerQueries(self, nums: list[int], queries: list[int]) -> list[int]:
    nums.sort()

    def numOfElementsLessThan(query: int) -> int:
      summ = 0
      for i, num in enumerate(nums):
        summ += num
        if summ > query:
          return i
      return len(nums)

    return [numOfElementsLessThan(query) for query in queries]
 # code by PROGIEZ