LeetCode 2389 - Longest Subsequence With Limited Sum

This problem asks us to determine, for each query, the maximum number of elements we can select from an array nums such that their sum does not exceed a given value.

leetcodeeasyarraybinary-searchgreedysortingprefix-sum

LeetCode Problem 2389

Difficulty: 🟢 Easy
Topics: Array, Binary Search, Greedy, Sorting, Prefix Sum

Solution

Problem Understanding

This problem asks us to determine, for each query, the maximum number of elements we can select from an array nums such that their sum does not exceed a given value. We are not required to maintain consecutive elements, only the relative order for subsequences, but in this problem the relative order does not impact the sum because we can choose any combination of elements. The inputs are two integer arrays, nums of length n and queries of length m, both with values ranging from 1 to 10^6. The output is an array of integers, where each entry corresponds to the maximum subsequence length achievable under the corresponding query sum constraint.

Important edge cases include queries that are smaller than the smallest element in nums (resulting in a subsequence of length 0), queries that are larger than the sum of all elements (resulting in the full array), and arrays with only one element. The constraints (n, m <= 1000) indicate that we can afford O(n log n) or O(n * m) solutions comfortably, but O(2^n) brute-force solutions would be infeasible.

Approaches

The brute-force approach would involve generating all subsequences of nums for each query and computing their sums. We would then select the longest subsequence whose sum does not exceed the query. While this guarantees correctness, it is exponentially slow (O(2^n * m)) and impractical for n = 1000.

The optimal approach leverages the observation that the maximum-length subsequence under a sum constraint is obtained by choosing the smallest numbers first. This leads to sorting nums in ascending order and using prefix sums to quickly compute the total sum of the first k numbers. For each query, we then find the largest k such that the prefix sum of the first k elements is less than or equal to the query. Binary search can efficiently determine k for each query.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * 2^n) O(n) Generate all subsequences for each query, infeasible for n > 20
Optimal O(n log n + m log n) O(n) Sort array, compute prefix sums, use binary search for each query

Algorithm Walkthrough

  1. Sort the nums array in ascending order. This ensures that adding elements sequentially will maximize the number of elements we can include without exceeding a sum.
  2. Compute the prefix sums of nums. Let prefix[i] represent the sum of the first i+1 elements. This allows constant-time sum computation for any contiguous subset starting from the beginning.
  3. For each query, use binary search on the prefix sums array to find the largest index i such that prefix[i] <= query. This index + 1 gives the maximum subsequence length.
  4. Collect the results for all queries into the output array and return it.

Why it works: Sorting ensures that the smallest numbers are considered first, which maximizes the count under a sum limit. Prefix sums allow us to efficiently check the sum of the first k elements. Binary search guarantees we find the maximum k for each query efficiently.

Python Solution

from typing import List
import bisect

class Solution:
    def answerQueries(self, nums: List[int], queries: List[int]) -> List[int]:
        nums.sort()
        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]
        
        answer = []
        for query in queries:
            index = bisect.bisect_right(prefix_sums, query)
            answer.append(index)
        return answer

The Python implementation first sorts the array and computes the prefix sums. We then iterate through each query, using bisect_right to find the insertion point where the query would exceed the prefix sum. This index is exactly the maximum subsequence length for that query. Using bisect_right ensures correctness even when the query matches a prefix sum exactly.

Go Solution

import "sort"

func answerQueries(nums []int, queries []int) []int {
    sort.Ints(nums)
    prefixSums := make([]int, len(nums))
    prefixSums[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        prefixSums[i] = prefixSums[i-1] + nums[i]
    }

    answer := make([]int, len(queries))
    for i, query := range queries {
        left, right := 0, len(prefixSums)
        for left < right {
            mid := (left + right) / 2
            if prefixSums[mid] <= query {
                left = mid + 1
            } else {
                right = mid
            }
        }
        answer[i] = left
    }
    return answer
}

In Go, we manually implement binary search to find the largest index i with prefixSums[i] <= query. This avoids using additional packages for bisect operations. The logic mirrors the Python version, but we handle slices and indices explicitly.

Worked Examples

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

After sorting, nums = [1,2,4,5]. Prefix sums: [1,3,7,12].

Query Binary Search Result Explanation
3 2 Prefix sums ≤ 3 are [1,3], length = 2
10 3 Prefix sums ≤ 10 are [1,3,7], length = 3
21 4 Prefix sums ≤ 21 are [1,3,7,12], length = 4

Example 2: nums = [2,3,4,5], queries = [1]

Sorted: [2,3,4,5]. Prefix sums: [2,5,9,14]. Query 1 is less than the smallest element, so result is 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + m log n) Sorting takes O(n log n), computing prefix sums O(n), binary search for m queries O(m log n)
Space O(n) Prefix sum array stores n integers, plus O(m) output array

The dominant factors are sorting and the binary search for each query, both efficient under the problem constraints.

Test Cases

# Provided examples
assert Solution().answerQueries([4,5,2,1], [3,10,21]) == [2,3,4]  # basic case
assert Solution().answerQueries([2,3,4,5], [1]) == [0]  # query smaller than min element

# Edge cases
assert Solution().answerQueries([1], [1]) == [1]  # single element equal to query
assert Solution().answerQueries([1], [0]) == [0]  # single element greater than query
assert Solution().answerQueries([5,5,5,5], [10,15,20]) == [2,3,4]  # all same elements
assert Solution().answerQueries([1,2,3,4,5], [15]) == [5]  # sum of all elements equals query
Test Why
[4,5,2,1], [3,10,21] Validates standard functionality
[2,3,4,5], [1] Query smaller than smallest element
[1], [1] Single element equal to query
[1], [0] Single element greater than query
[5,5,5,5], [10,15,20] Duplicates in array
[1,2,3,4,5], [15] Query equals sum of all elements

Edge Cases

One edge case is when all elements in nums are larger than the query. In this scenario, the maximum subsequence length is 0. Sorting and binary search correctly handle this because the first prefix sum exceeds the query.

Another edge case occurs when the query is larger than the sum of all elements in nums. The algorithm returns the full length of nums, as binary search will go past the last index.

A third edge case is when nums contains duplicate numbers. Sorting and prefix sums naturally accumulate duplicates, and binary search correctly accounts for them, ensuring that the length calculation includes all usable elements.

This solution handles all these edge cases efficiently and correctly.