Problem Statement

You are given an integer array nums of length n, and an integer array queries of length m.

For each queries[i], you need to determine the maximum length of a subsequence of nums such that the sum of the subsequence is less than or equal to queries[i].

A subsequence is derived from the array by deleting some or no elements without changing the order of the remaining elements.

Return an array result of length m where result[i] is the answer to the i-th query.

Examples

Example 1:

Input: nums = [4, 2, 1, 5], queries = [3, 7, 9]
Output: [2, 3, 4]

Explanation:
For queries[0] = 3, the longest subsequence we can pick is [2, 1] with sum = 3, so the result is 2.
For queries[1] = 7, the longest subsequence we can pick is [4, 2, 1] with sum = 7, so the result is 3.
For queries[2] = 9, the longest subsequence we can pick is [4, 2, 1, 5] with sum = 9, so the result is 4.

Example 2:

Input: num = [2, 3, 4, 5], queries = [1]
Output: [0]

Explanation:
No subsequence can be formed with sum <= 1

Different Approaches

1️⃣ Brute Force Approach (Greedy + Sorting)

Intuition:

• The main idea is to first sort the nums array to handle smaller numbers first, as smaller numbers are easier to fit into the subsequence without exceeding the sum limit.
• For each query, we can check how many elements from the sorted nums can be added until the sum exceeds the query value.

Steps:

1. Sort the nums array.
2. For each query:
   • Start adding the elements from the sorted nums until the sum exceeds the query value.
   • Count the number of elements added that remain under the query sum limit.

Approach:

1. Sort the nums array in non-decreasing order.
2. For each query:
   • Traverse through the sorted array and keep a running sum.
   • If adding an element does not exceed the query, continue adding it to the subsequence.
   • Stop when the sum exceeds the query and return the count of elements added.

Code:

#include <vector>
#include <algorithm>

using namespace std;

vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
    // Sort the nums array to process the smallest elements first
    sort(nums.begin(), nums.end());

    vector<int> result;  // This will store the result for each query
    
    // Process each query one by one
    for (int query : queries) {
        int count = 0;
        int sum = 0;
        
        // Traverse through the sorted nums array and check how many can be added
        for (int num : nums) {
            sum += num;
            if (sum <= query) {
                count++;  // We can add this element to the subsequence
            } else {
                break;   // If sum exceeds the query, stop
            }
        }
        
        // Store the result for this query
        result.push_back(count);
    }
    
    return result;
}

Complexity Analysis:

• Time Complexity: O(n log n + m*n)
  • Sorting the nums array takes O(n log n).
  • For each query, we iterate through the sorted nums array, which takes O(n) for each query. Since there are m queries, this part takes O(m * n).
  • Total Complexity: O(n log n + m * n).
• Space Complexity: O(n)
  • Due to sorting the array in place.

2️⃣ Prefix Sum + Binary Search

Intuition:

• Once the array is sorted, we can calculate the prefix sum. The idea is to utilize the fact that prefix sums allow us to quickly check the sum of any subsequence that includes the smallest elements of the sorted array.
• For each query, we can binary search on the prefix sums to find the longest subsequence whose sum is less than or equal to the query value.

Steps:

1. Sort the nums array.
2. Calculate the prefix sum array.
3. For each query, perform a binary search on the prefix sum array to find the maximum length of the subsequence that satisfies the query.

Approach:

1. Sort the nums array.
2. Create a prefix sum array where each element at index i represents the sum of the first i elements of the sorted nums.
3. For each query, use binary search to find the largest index k such that the prefix sum is less than or equal to the query.

Code:

#include <vector>
#include <algorithm>

using namespace std;

// Custom binary search to find the upper bound manually
int upperBound(const vector<int>& prefixSums, int target) {
    int low = 0;
    int high = prefixSums.size() - 1;
    int ans = prefixSums.size();  // If target is larger than any prefix sum, return size of array
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (prefixSums[mid] <= target) {
            low = mid + 1;  // Move to the right half if current sum is ≤ target
        } else {
            ans = mid;      // Store current index as potential answer
            high = mid - 1; // Move to the left half
        }
    }
    
    return ans;
}

vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
    // Step 1: Sort the nums array
    sort(nums.begin(), nums.end());

    // Step 2: Build prefix sums
    int n = nums.size();
    vector<int> prefixSums(n, 0);
    prefixSums[0] = nums[0];
    
    for (int i = 1; i < n; i++) {
        prefixSums[i] = prefixSums[i-1] + nums[i];
    }

    vector<int> result;
    
    // Step 3: Process each query using binary search on the prefix sums
    for (int query : queries) {
        // Use manual binary search to find the largest subsequence length
        int maxLength = upperBound(prefixSums, query);
        result.push_back(maxLength);
    }
    
    return result;
}

Complexity Analysis:

• Time Complexity: O(n log n)
  • Sorting takes O(n log n)
  • Constructing the prefix sum array takes O(n)
  • For each query, binary search takes O(log n), so the total complexity is O(n log n + m log n).
• Space Complexity:
  • The space complexity isO(n) for storing the prefix sum array.