We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Subsequence With Limited Sum

Difficulty: Easy

Problem Description

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.

Key Insights

  • The problem requires finding the maximum size of subsequences whose sums are limited by the values in the queries array.
  • Sorting the nums array allows us to efficiently calculate the prefix sums.
  • Using prefix sums, we can quickly determine how many elements can be included without exceeding each query's sum limit.
  • Binary search can be employed on the prefix sums to find the maximum number of elements that can be included for each query.

Space and Time Complexity

Time Complexity: O(n log n + m log n)
Space Complexity: O(n)

Solution

To solve this problem, we can use a combination of sorting and prefix sums. First, we sort the nums array. Then, we compute the prefix sums of the sorted array, which allows us to quickly check how many elements can be included for each query. For each query, we can use binary search to find the maximum index in the prefix sums that is less than or equal to the query value. This approach ensures that we efficiently determine the maximum size of the subsequences.

Code Solutions

def maxSubsequenceSize(nums, queries):
    # Sort the nums array
    nums.sort()
    # Compute prefix sums
    prefix_sums = [0] * len(nums)
    prefix_sums[0] = nums[0]
    for i in range(1, len(nums)):
        prefix_sums[i] = prefix_sums[i - 1] + nums[i]
    
    # Result list
    result = []
    for query in queries:
        # Binary search for the largest index where the prefix sum is <= query
        left, right = 0, len(prefix_sums) - 1
        while left <= right:
            mid = (left + right) // 2
            if prefix_sums[mid] <= query:
                left = mid + 1
            else:
                right = mid - 1
        # The size of the subsequence is the index found
        result.append(left)
    
    return result
← Back to All Questions