algoadvance

Leetcode 2389. Longest Subsequence With Limited Sum

Problem Statement

We are given an array of integers nums and an array of integers queries. For each query in queries, we need to determine the length of the longest subsequence in nums such that the sum of the elements in the subsequence is less than or equal to the query value.

The function signature is:

vector<int> answerQueries(vector<int>& nums, vector<int>& queries);

Clarifying Questions

  1. Subsequences Definition: Are these subsequences required to be contiguous?
    • No, any element can be included as long as the total sum is within the query limit.
  2. Range Constraints: What are the constraints on the size of nums and the values within nums and queries?
    • Typically, LeetCode problems provide constraints. For this problem, let’s assume:
      • 1 <= nums.length, queries.length <= 1000
      • 1 <= nums[i], queries[i] <= 10^6
  3. Output: What should the function return?
    • The function should return a vector of integers where each integer corresponds to the length of the longest subsequence for each query.

Strategy

  1. Sort nums: Sorting the array will help us consider the smallest elements first, which allows us to maximize the number of elements included in the subsequence without exceeding the query sum.
  2. Cumulative Sum: Calculate the cumulative sum of the sorted nums to easily determine how many elements can be included without exceeding each query value in queries.
  3. Binary Search: For each query, use binary search on the cumulative sum array to efficiently determine the maximum number of elements that can be included.

Code

#include <vector>
#include <algorithm> // For sort and lower_bound
using namespace std;

vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
    // Sort the nums array to consider smallest elements first
    sort(nums.begin(), nums.end());
    
    // Compute the prefix sums of the sorted nums array
    vector<int> prefixSums(nums.size(), 0);
    prefixSums[0] = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        prefixSums[i] = prefixSums[i-1] + nums[i];
    }

    // Result vector to store the answer for each query
    vector<int> result(queries.size(), 0);

    // Process each query
    for (int i = 0; i < queries.size(); ++i) {
        int query = queries[i];
        
        // Use binary search to find the maximum index where prefixSum is <= query
        auto it = upper_bound(prefixSums.begin(), prefixSums.end(), query);
        
        // Distance from the prefixSums beginning to the position found is the length
        result[i] = distance(prefixSums.begin(), it);
    }

    return result;
}

Time Complexity

  1. Sorting: Sorting the nums array takes (O(n \log n)), where (n) is the length of nums.
  2. Prefix Sum Calculation: This takes (O(n)).
  3. Binary Search for Each Query: Each query is processed in (O(\log n)) due to the binary search on the cumulative sums.
  4. Total Time Complexity: The overall time complexity is (O(n \log n + q \log n)), where (q) is the length of queries.

This approach ensures that we efficiently determine the longest subsequence for each query, balancing both time complexity and clarity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI