{x}
blog image

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

Solution Explanation: Longest Subsequence With Limited Sum

The problem asks to find the maximum size of a subsequence in nums whose sum is less than or equal to each query in queries. The most efficient solution involves sorting and utilizing either binary search or a two-pointer approach.

Core Idea: Since we want to maximize the subsequence length, we should always prioritize selecting smaller numbers. This leads us to sort nums in ascending order.

Solution 1: Sorting + Prefix Sum + Binary Search

  1. Sort nums: Sort the nums array in ascending order. This ensures that we always consider smaller numbers first.

  2. Calculate Prefix Sum: Create a prefix sum array s. s[i] will store the sum of elements from nums[0] to nums[i]. This allows for efficient calculation of the sum of a subsequence.

  3. Binary Search for Each Query: For each query q in queries:

    • Perform a binary search on the s array to find the largest index j such that s[j] <= q.
    • The value j + 1 represents the maximum length of the subsequence whose sum is less than or equal to q.

Time Complexity: O((n + m)log n), where n is the length of nums and m is the length of queries. Sorting takes O(n log n), and each binary search takes O(log n).

Space Complexity: O(n) to store the prefix sum array.

Solution 2: Sorting + Offline Query + Two Pointers

This approach optimizes the process by first sorting the queries based on their values. This avoids redundant calculations.

  1. Sort nums: Sort nums in ascending order.

  2. Sort Queries (Indirectly): Create an index array idx where idx[i] = i. Sort idx based on the values in queries in ascending order. This allows processing queries in increasing order of their limits.

  3. Two Pointers: Use a two-pointer approach:

    • s: keeps track of the current sum of the subsequence.
    • j: points to the next element to potentially add to the subsequence.
    • Iterate through the sorted idx array. For each query queries[idx[i]]:
      • Incrementally add elements from nums (starting from index j) to the current subsequence (s) until s exceeds queries[idx[i]].
      • The value of j at this point represents the length of the maximum subsequence satisfying the condition for queries[idx[i]]. Store this in the ans array at the appropriate index.

Time Complexity: O(n log n + m log m), where the n log n comes from sorting nums and m log m from sorting idx based on queries. The two-pointer iteration is linear in n and m combined (in the worst case). It can be considered O(n+m) if we consider the sorting cost as pre-processing.

Space Complexity: O(m) to store idx and ans arrays.

The choice between Solution 1 and Solution 2 depends on the relative sizes of n and m. If m is significantly smaller than n, Solution 1 might be slightly faster due to fewer sorting operations. If m is comparable to or larger than n, Solution 2 might be more efficient because it avoids repeated calculations for similar queries.

Note: The provided code snippets in multiple languages demonstrate both solutions. Remember to choose the appropriate solution based on the specific constraints and performance requirements. The _ in some TypeScript and JavaScript solutions implies the use of a library (like Lodash) that provides efficient sorted index functionality which internally uses binary search. You can replace that with a manual binary search implementation if desired.