Skip to content

2389. Longest Subsequence With Limited Sum 👍

  • Time: $O(\texttt{sort}(\texttt{nums}) + qn)$
  • Space: $O(q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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]