2389.longest-subsequence-with-limited-sum.md

2389. Longest Subsequence With Limited Sum

Key Insights

To find the subsequence that sums up to threshold (queries[i]):

nums = [3, 1, 4, 2]
threshold = 6

There are 2 subsequences that sum up to 6:

[3, 1, 4, 2]
 O  O     O

[3, 1, 4, 2]
       O  O

A subsequence is any subset of the array, regardless of the order, so to maximum size of a subsequence that you can take from nums under the threshold, the best way is:

• Sort the array in ascending order.
• Take from the smallest element until the sum exceeds the threshold. (greedy)

The best subsequence is just the first K smallest elements, that is the prefix sum of the sorted array.

nums = [1, 2, 3, 4]
        1 +2 +3 = 6
threshold = 6

Even this problems is asking for the longest subsequence, we can sort the array first, then the problem becomes to find the longest subarray (prefix) that sums up <= threshold. It's similar to the key idea in 2779. Maximum Beauty of an Array After Applying Operation.

Let's walk through the example:

nums = [4, 2, 1, 3]
queries = [4, 10, 21]

After sorting:
[1, 2, 3, 4]
[1, 3, 6, 10] // prefix sum

Query: 4, max subarray sum <= 4, result = [1, 2]
Query: 10, max subarray sum <= 10, result = [1, 3, 6]
Query: 21, max subarray sum <= 21, result = [1, 3, 6, 10]

Prefix Sum + Binary Search

We can build the prefix sum array first, then for each query, we can use binary search to find the longest subarray that sums up <= threshold.

 0  1  2  3 // index
[1, 3, 6, 10] // prefix sum

Query: 4, binary search, find the first element > 4, result = 2
Query: 10, binary search, find the first element > 10, result = 4
Query: 21, binary search, find the first element > 21, result = 4

fun answerQueries(nums: IntArray, queries: IntArray): IntArray {
    nums.sort()
    for (i in 1 until nums.size) {
        nums[i] += nums[i - 1]
    }

    val ans = IntArray(queries.size)
    for (q in queries.indices) {
        val index = binarySearch(nums, queries[q])
        ans[q] = index
    }
    return ans
}

// Find the first element > target
// Or we can find the last element <= target
fun binarySearch(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        val isValid = nums[middle] > target
        if (isValid) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

• Time Complexity: O(n * log(n) + m * log(n)), where n is the length of nums and m is the length of queries.
• Space Complexity: O(1)

Brute Force

fun answerQueries(nums: IntArray, queries: IntArray): IntArray {
    nums.sort()
    val n = nums.size
    val m = queries.size
    val ans = IntArray(m)
    for (i in queries.indices) {
        val max = queries[i]
        var j = 0
        var sum = 0
        while (j < n && sum + nums[j] <= max) {
            sum += nums[j]
            j++
        }
        ans[i] = j
    }
    return ans
}

• Time Complexity: O(n * m)
• Space Complexity: O(1)