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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Subsequence With Limited Sum

Number: 2469

Difficulty: Easy

Paid? No

Companies: Adobe

Problem Description

Given an integer array nums and an integer array queries, return an array answer where answer[i] is the maximum size of a subsequence that can be taken from nums such that the sum of its elements is less than or equal to queries[i]. A subsequence is an array derived from another array by deleting some or no elements without changing the order of the remaining elements.

Key Insights

  • Sorting nums allows us to include the smallest elements first, maximizing the subsequence size.
  • Building a prefix sum array from the sorted nums helps quickly determine the sum of the smallest k elements.
  • Binary search on the prefix sum array efficiently finds the maximum number of elements that can sum up to a given query value.
  • Combining sorting (O(n log n)) and binary search for each query (O(m log n)) results in an efficient solution.

Space and Time Complexity

Time Complexity: O(n log n + m log n)
Space Complexity: O(n) for the prefix sum array

Solution

First, sort the nums array to have the smallest elements at the beginning. Next, compute a prefix sum array where each entry represents the cumulative sum of the smallest elements up to that index. For each query, use binary search on the prefix sum array to find the largest index where the cumulative sum is less than or equal to the query value. This index corresponds to the maximum size of the subsequence that fits within the query sum.

Code Solutions

def answerQueries(nums, queries):
    # Sort nums to ensure we add smallest numbers first
    nums.sort()
    
    n = len(nums)
    # Create a prefix sum array where prefix[i] is the sum of the first i elements
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    
    # Helper function: binary search for the maximum index such that prefix[index] <= target
    def binary_search(target):
        low, high = 0, n
        ans = 0
        while low <= high:
            mid = (low + high) // 2
            if prefix[mid] <= target:
                ans = mid
                low = mid + 1
            else:
                high = mid - 1
        return ans
    
    # Process each query using the helper binary search
    result = [binary_search(q) for q in queries]
    return result

# Example usage:
nums = [4, 5, 2, 1]
queries = [3, 10, 21]
print(answerQueries(nums, queries))  # Expected output: [2, 3, 4]
← Back to All Questions