Longest Subsequence With Limited Sum

Easy

Asked by:

16 views

Topics:

ArraysGreedy AlgorithmsBinary Search

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] <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `nums` array and the `queries` array?
Can the values in the `nums` array and the `queries` array be negative, zero, or non-integer values?
If multiple subsequences with the same maximum length satisfy a query, can I return any one of those lengths?
Are there any specific memory constraints I should be aware of, given the potential size of the inputs?
Is the `nums` array sorted, or should I assume it is unsorted and needs to be sorted for optimal performance?

Brute Force Solution

Approach

The brute force approach to finding the longest subsequence with a limited sum involves trying every possible combination of numbers. We check each combination to see if its sum is within the limit. We then keep track of the longest sequence we found that meets the sum limit.

Here's how the algorithm would work step-by-step:

Consider every possible group of numbers from the input.
Calculate the total value of each group of numbers.
If the total value of the group is less than or equal to the given limit, it's a valid group.
Among all the valid groups, find the one with the most numbers in it.
The group with the most numbers that stays within the limit is the longest subsequence with a limited sum.

Code Implementation

def longest_subsequence_with_limited_sum_brute_force(numbers, limit):
    longest_subsequence_length = 0

    # Iterate through all possible subsequences
    for i in range(1 << len(numbers)):
        current_subsequence = []

        # Build the current subsequence based on the bitmask
        for j in range(len(numbers)):
            if (i >> j) & 1:
                current_subsequence.append(numbers[j])

        #Calculate sum of current subsequence
        current_sum = sum(current_subsequence)

        # Check if sum is within the limit
        if current_sum <= limit:

            #Update if this is the longest valid subsequence so far
            longest_subsequence_length = max(longest_subsequence_length, len(current_subsequence))

    return longest_subsequence_length

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach considers every possible subsequence of the input array. For an array of size n, there are 2^n possible subsequences (each element can either be included or excluded). For each subsequence, we calculate the sum of its elements, which takes O(n) time in the worst case. Therefore, the overall time complexity is O(n * 2^n). Because 2^n grows much faster than n, we can simplify this to O(2^n) as the dominant factor.

Space Complexity

O(1) – The brute force approach considers every possible subsequence from the input numbers. However, the plain English explanation does not explicitly mention creating additional data structures to store all these subsequences. It only focuses on calculating the sum of each subsequence and comparing its length with the current longest valid subsequence's length. Therefore, the space complexity is dominated by a few variables used for sum calculation and length tracking, which is constant regardless of the input size N (the number of input numbers).

Optimal Solution

Approach

The best way to find the longest subsequence is to first sort the numbers from smallest to largest. Then, for each limit, we greedily take as many of the smallest numbers as we can without exceeding that limit. This guarantees we get the longest possible subsequence for that limit.

Here's how the algorithm would work step-by-step:

First, arrange all the available numbers in increasing order, from smallest to largest.
For each given limit, start adding numbers from the beginning of the sorted list (the smallest numbers) to a running total.
Keep adding numbers as long as the running total is less than or equal to the limit.
Count how many numbers you were able to add before exceeding the limit. This is the length of the longest subsequence for that limit.
Repeat the process for each of the other limits, always starting with the sorted list of numbers.

Code Implementation

def longest_subsequence(numbers, queries):
    numbers.sort()
    result = []

    for query in queries:
        current_sum = 0
        count = 0

        #Greedily add smallest elements
        for number in numbers:
            if current_sum + number <= query:
                current_sum += number
                count += 1
            else:
                break

        result.append(count)

    return result

Big(O) Analysis

Time Complexity

O(n log n + m * n) – Sorting the input array of size n takes O(n log n) time. After sorting, we iterate through each of the m limits. For each limit, we iterate through the sorted array of size n, summing elements until the limit is reached or the array is exhausted. Thus, the nested loop operation takes O(m * n) time. Combining both operations, the total time complexity is O(n log n + m * n). If m is much smaller than log(n), the time complexity is dominated by O(n log n); conversely, if m is relatively big the time complexity is dominated by O(m*n).

Space Complexity

O(1) – The algorithm sorts the input array in place, which does not require auxiliary space if an in-place sorting algorithm is used. The algorithm then iterates through the sorted array and the queries, using a few variables to store the running sum and the length of the subsequence. Since the number of extra variables used does not depend on the size of the input array or the number of queries, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty nums array or empty queries array	Return an empty result array immediately as there are no numbers to process or no queries to answer.
nums array contains negative numbers	The problem statement implies non-negative integers, so clarify the constraint; if negatives are allowed, the solution needs to handle them (e.g., using absolute values or adjusting the logic).
queries array contains zero or very small values	The longest subsequence will likely be empty or very short; the solution should correctly identify these cases without errors.
nums array contains extremely large numbers close to the maximum integer value	Potential integer overflow in prefix sum calculations; use a larger data type (long) if necessary.
queries array contains extremely large values exceeding the sum of all nums	The result should be the length of the entire nums array, as all elements can be included in the subsequence.
nums array contains duplicate numbers of varying frequencies	The sorting approach will handle duplicates correctly, as the order of elements with the same value does not affect the final subsequence length.
nums array is very large (e.g., 10^5) and queries array is also very large	Sorting nums is O(n log n), and each query is O(n) for a brute-force prefix sum approach; a more efficient approach (e.g., binary search after sorting) is needed to avoid exceeding time limits.
All numbers in the nums array are zero	The longest subsequence will be the length of nums if the query value is non-zero, and 0 if the query value is zero, and this should be handled correctly.

Empty nums array or empty queries array

How to Handle:

Return an empty result array immediately as there are no numbers to process or no queries to answer.

nums array contains negative numbers

How to Handle:

The problem statement implies non-negative integers, so clarify the constraint; if negatives are allowed, the solution needs to handle them (e.g., using absolute values or adjusting the logic).

queries array contains zero or very small values

How to Handle:

The longest subsequence will likely be empty or very short; the solution should correctly identify these cases without errors.

nums array contains extremely large numbers close to the maximum integer value

How to Handle:

Potential integer overflow in prefix sum calculations; use a larger data type (long) if necessary.

queries array contains extremely large values exceeding the sum of all nums

How to Handle:

The result should be the length of the entire nums array, as all elements can be included in the subsequence.

nums array contains duplicate numbers of varying frequencies

How to Handle:

The sorting approach will handle duplicates correctly, as the order of elements with the same value does not affect the final subsequence length.

nums array is very large (e.g., 10^5) and queries array is also very large

How to Handle:

Sorting nums is O(n log n), and each query is O(n) for a brute-force prefix sum approach; a more efficient approach (e.g., binary search after sorting) is needed to avoid exceeding time limits.

All numbers in the nums array are zero

How to Handle:

The longest subsequence will be the length of nums if the query value is non-zero, and 0 if the query value is zero, and this should be handled correctly.