2389. Longest Subsequence With Limited Sum Solution

The problem

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⁶

Approach overview

Problem Overview: You get an integer array nums and multiple query values. For each query, return the maximum length of a subsequence whose total sum is less than or equal to that query. The subsequence can contain any elements from the array but must respect the sum constraint.

Approach 1: Greedy with Sorting and Prefix Sum (Time: O(n log n + n·q), Space: O(n))

The key observation: to maximize subsequence length under a sum limit, you should always pick the smallest numbers first. Sort the array using sorting. After sorting, compute a prefix sum array where prefix[i] represents the sum of the smallest i+1 numbers. For each query, iterate through the prefix array and find the largest index where the prefix sum is ≤ the query value. That index + 1 is the maximum subsequence length you can build.

This works because any larger number would increase the sum faster and reduce how many elements you can include. The greedy choice of always taking the smallest available numbers guarantees the longest valid subsequence. This approach is easy to implement but scanning the prefix array for every query leads to O(n) work per query.

Approach 2: Binary Search on Prefix Sums (Time: O(n log n + q log n), Space: O(n))

After sorting the array and building the prefix sums, the prefix array becomes monotonically increasing. That property allows you to apply binary search. For each query, perform a binary search on the prefix array to find the rightmost index where prefix[i] ≤ query. The position of that index determines the maximum number of elements you can include.

Binary search reduces each query from O(n) to O(log n). The preprocessing step (sorting and building prefix sums) still takes O(n log n), but query handling becomes much faster for large input sizes. This pattern—sort → prefix sum → binary search—is common in problems where you repeatedly check cumulative limits.

Recommended for interviews: Start by explaining the greedy idea: choosing the smallest numbers maximizes how many elements fit under the sum constraint. Build prefix sums to track cumulative totals. The optimal implementation uses binary search on the prefix array, achieving O(n log n + q log n). Mentioning the linear scan version first shows you understand the structure of the problem, while the binary search optimization demonstrates strong knowledge of array processing and query optimization.

Approach 1: Greedy Approach with Sorting and Prefix Sum

By sorting the nums array, the subsequences with the smallest sums can be easily constructed. Calculating a prefix sum for the sorted array helps in determining how many elements can be included before the sum exceeds the query limit.

Python

from bisect import bisect_right

class Solution:
    def answerQueries(self, nums, queries):
        nums.sort()
        prefix_sum = [0] * len(nums)
        prefix_sum[0] = nums[0]
        for i in range(1, len(nums)):
            prefix_sum[i] = prefix_sum[i - 1] + nums[i]

        answer = []
        for q in queries:
            count = bisect_right(prefix_sum, q)
            answer.append(count)
        return answer

Java

import java.util.Arrays;

public class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int[] prefixSum = new int[nums.length];
        prefixSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }
        
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                if (prefixSum[j] <= queries[i]) {
                    count = j + 1;
                } else {
                    break;
                }
            }
            answer[i] = count;
        }
        return answer;
    }
}

C++

#include <vector>
#include <algorithm>

std::vector<int> answerQueries(std::vector<int>& nums, std::vector<int>& queries) {
    std::sort(nums.begin(), nums.end());
    std::vector<int> prefixSum = nums;
    for (size_t i = 1; i < nums.size(); i++) {
        prefixSum[i] += prefixSum[i - 1];
    }
    
    std::vector<int> answer;
    for (int q : queries) {
        int count = std::upper_bound(prefixSum.begin(), prefixSum.end(), q) - prefixSum.begin();
        answer.push_back(count);
    }
    return answer;
}

JavaScript

var answerQueries = function(nums, queries) {
    nums.sort((a, b) => a - b);
    for(let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    
    return queries.map(q => {
        let count = 0;
        for(let sum of nums){
            if(sum <= q){
                count++;
            } else {
                break;
            }
        }
        return count;
    });
};

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int* answerQueries(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    
    int* prefixSum = (int*)malloc(numsSize * sizeof(int));
    prefixSum[0] = nums[0];
    for (int i = 1; i < numsSize; i++) {
        prefixSum[i] = prefixSum[i - 1] + nums[i];
    }
    
    int* answer = (int*)malloc(queriesSize * sizeof(int));
    for (int i = 0; i < queriesSize; i++) {
        int q = queries[i];
        int count = 0;
        for (int j = 0; j < numsSize; j++) {
            if (prefixSum[j] <= q) {
                count = j + 1;
            } else {
                break;
            }
        }
        answer[i] = count;
    }
    
    *returnSize = queriesSize;
    free(prefixSum);
    return answer;
}

using System;
using System.Linq;

public class Solution {
    public int[] AnswerQueries(int[] nums, int[] queries) {
        Array.Sort(nums);
        int[] prefixSum = new int[nums.Length];
        prefixSum[0] = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }

        int[] answer = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int count = Array.FindLastIndex(prefixSum, x => x <= queries[i]) + 1;
            answer[i] = count;
        }
        return answer;
    }
}

The Python solution makes use of bisect_right to find the breakpoint in the prefix sums for each query, providing the maximum size of a subsequence that fits.

Complexity

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(n) for the prefix sum array.

Try this approach in the editor

Approach 2: Binary Search Optimization

This approach extends the prefix sum method by using binary search to efficiently find where the query fits within the prefix sum array. This reduces the time complexity significantly, especially for large inputs.

Python

from bisect import bisect_right

class Solution:
    def answerQueries(self, nums, queries):
        nums.sort()
        for i in range(1, len(nums)):
            nums[i] += nums[i-1]

        return [bisect_right(nums, q) for q in queries]

Java

import java.util.Arrays;

public class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int[] prefixSum = new int[nums.length];
        prefixSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }

        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int left = 0, right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (prefixSum[mid] <= queries[i]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            answer[i] = left;
        }
        return answer;
    }
}

C++

#include <vector>
#include <algorithm>

std::vector<int> answerQueries(std::vector<int>& nums, std::vector<int>& queries) {
    std::sort(nums.begin(), nums.end());
    std::vector<int> prefixSum(nums);
    for (size_t i = 1; i < nums.size(); i++) {
        prefixSum[i] += prefixSum[i - 1];
    }

    std::vector<int> answer(queries.size());
    for (size_t i = 0; i < queries.size(); i++) {
        int count = std::upper_bound(prefixSum.begin(), prefixSum.end(), queries[i]) - prefixSum.begin();
        answer[i] = count;
    }
    return answer;
}

JavaScript

var answerQueries = function(nums, queries) {
    nums.sort((a, b) => a - b);
    for(let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }

    return queries.map(q => {
        let left = 0, right = nums.length - 1;
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            if (nums[mid] <= q) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    });
};

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int binarySearch(int* prefixSum, int size, int q) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (prefixSum[mid] <= q)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return left;
}

int* answerQueries(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) {
    qsort(nums, numsSize, sizeof(int), compare);

    int* prefixSum = (int*)malloc(numsSize * sizeof(int));
    prefixSum[0] = nums[0];
    for (int i = 1; i < numsSize; i++) {
        prefixSum[i] = prefixSum[i - 1] + nums[i];
    }

    int* answer = (int*)malloc(queriesSize * sizeof(int));
    for (int i = 0; i < queriesSize; i++) {
        answer[i] = binarySearch(prefixSum, numsSize, queries[i]);
    }

    *returnSize = queriesSize;
    free(prefixSum);
    return answer;
}

using System;

public class Solution {
    public int[] AnswerQueries(int[] nums, int[] queries) {
        Array.Sort(nums);
        int n = nums.Length;
        for (int i = 1; i < n; i++) {
            nums[i] += nums[i-1];
        }

        int[] answer = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int left = 0, right = n - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] <= queries[i]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            answer[i] = left;
        }
        return answer;
    }
}

The solution utilizes the Python bisect_right method to perform a binary search on the prefix sums, swiftly determining the amount of numbers that sum up to less than or equal to each query limit.

Complexity

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) additional space apart from inputs and outputs.

Try this approach in the editor

Approach 3: Sorting + Prefix Sum + Binary Search

According to the problem description, for each queries[i], we need to find a subsequence such that the sum of its elements does not exceed queries[i] and the length of the subsequence is maximized. Obviously, we should choose the smallest possible elements to maximize the length of the subsequence.

Therefore, we can first sort the array nums in ascending order, and then for each queries[i], we can use binary search to find the smallest index j such that nums[0] + nums[1] + cdots + nums[j] > queries[i]. At this point, nums[0] + nums[1] + cdots + nums[j - 1] is the sum of the elements of the subsequence that meets the condition, and the length of this subsequence is j. Therefore, we can add j to the answer array.

The time complexity is O((n + m) times log n), and the space complexity is O(n) or O(log n). Here, n and m are the lengths of the arrays nums and queries, respectively.

TypeScript

function answerQueries(nums: number[], queries: number[]): number[] {
    nums.sort((a, b) => a - b);
    for (let i = 1; i < nums.length; i++) {
        nums[i] += nums[i - 1];
    }
    return queries.map(q => _.sortedIndex(nums, q + 1));
}

func answerQueries(nums []int, queries []int) (ans []int) {
	sort.Ints(nums)
	for i := 1; i < len(nums); i++ {
		nums[i] += nums[i-1]
	}
	for _, q := range queries {
		ans = append(ans, sort.SearchInts(nums, q+1))
	}
	return
}

Rust

impl Solution {
    pub fn answer_queries(mut nums: Vec<i32>, queries: Vec<i32>) -> Vec<i32> {
        nums.sort();

        for i in 1..nums.len() {
            nums[i] += nums[i - 1];
        }

        queries.iter().map(|&q| {
            match nums.binary_search(&q) {
                Ok(idx) => idx as i32 + 1,
                Err(idx) => idx as i32,
            }
        }).collect()
    }
}

Try this approach in the editor

Approach 4: Sorting + Offline Query + Two Pointers

Similar to Solution 1, we can first sort the array nums in ascending order.

Next, we define an index array idx of the same length as queries, where idx[i] = i. Then, we sort the array idx in ascending order based on the values in queries. This way, we can process the elements in queries in ascending order.

We use a variable s to record the sum of the currently selected elements and a variable j to record the number of currently selected elements. Initially, s = j = 0.

We traverse the index array idx, and for each index i in it, we iteratively add elements from the array nums to the current subsequence until s + nums[j] \gt queries[i]. At this point, j is the length of the subsequence that meets the condition. We set the value of ans[i] to j and then continue to process the next index.

After traversing the index array idx, we obtain the answer array ans, where ans[i] is the length of the subsequence that satisfies queries[i].

The time complexity is O(n times log n + m), and the space complexity is O(m). Here, n and m are the lengths of the arrays nums and queries, respectively.

TypeScript

function answerQueries(nums: number[], queries: number[]): number[] {
    nums.sort((a, b) => a - b);
    const m = queries.length;
    const idx: number[] = new Array(m);
    for (let i = 0; i < m; i++) {
        idx[i] = i;
    }
    idx.sort((i, j) => queries[i] - queries[j]);
    const ans: number[] = new Array(m);
    let s = 0;
    let j = 0;
    for (const i of idx) {
        while (j < nums.length && s + nums[j] <= queries[i]) {
            s += nums[j++];
        }
        ans[i] = j;
    }
    return ans;
}

func answerQueries(nums []int, queries []int) (ans []int) {
	sort.Ints(nums)
	m := len(queries)
	idx := make([]int, m)
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(i, j int) bool { return queries[idx[i]] < queries[idx[j]] })
	ans = make([]int, m)
	s, j := 0, 0
	for _, i := range idx {
		for j < len(nums) && s+nums[j] <= queries[i] {
			s += nums[j]
			j++
		}
		ans[i] = j
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach with Sorting and Prefix Sum	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(n) for the prefix sum array.
Binary Search Optimization	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) additional space apart from inputs and outputs.
Sorting + Prefix Sum + Binary Search	–
Sorting + Offline Query + Two Pointers	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy with Sorting + Prefix Sum (Linear Scan)	O(n log n + n·q)	O(n)	Simple implementation when the number of queries is small
Prefix Sum + Binary Search	O(n log n + q log n)	O(n)	Best for large query counts; efficient lookups using sorted prefix sums

Frequently asked questions

Is Longest Subsequence With Limited Sum easy or hard?

Longest Subsequence With Limited Sum is classified as an Easy problem on LeetCode. The main idea is recognizing the greedy strategy of choosing the smallest numbers and using prefix sums to track cumulative totals. Adding binary search turns the solution into an efficient query-processing approach.

Longest Subsequence With Limited Sum Python/Java solution

Python and Java implementations follow the same steps: sort the array, compute prefix sums, and apply binary search for each query. Python typically uses the bisect module for binary search, while Java uses Arrays.binarySearch or a custom binary search implementation.

What is the best approach for Longest Subsequence With Limited Sum?

The most efficient approach sorts the array, builds a prefix sum array, and uses binary search for each query. Sorting ensures the smallest numbers are used first, which maximizes subsequence length. Binary search then finds the largest prefix whose sum is less than or equal to the query. The overall complexity is O(n log n + q log n).

Is Longest Subsequence With Limited Sum asked at Google/Amazon/Meta?

Problems using prefix sums, greedy selection, and binary search appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the pattern of sorting values and using prefix sums with binary search to answer range queries is very common in coding interviews.

What data structure is used in Longest Subsequence With Limited Sum?

The solution mainly uses arrays along with a prefix sum array derived from the sorted input. Binary search is applied to this prefix array to quickly locate the maximum valid subsequence length for each query.

What is the time complexity of Longest Subsequence With Limited Sum?

The optimal solution runs in O(n log n + q log n). Sorting the array takes O(n log n), building the prefix sum array takes O(n), and each query is answered with binary search in O(log n). A simpler implementation without binary search takes O(n log n + n·q).

How to solve Longest Subsequence With Limited Sum in O(n log n + q log n)?

Sort the array so smaller values are considered first. Build a prefix sum array where each index stores the cumulative sum of the sorted numbers. For each query, perform a binary search to find the rightmost prefix sum that is less than or equal to the query value. That index + 1 is the maximum subsequence length.

Longest Subsequence With Limited Sum solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Sorting and Prefix Sum

Approach 2: Binary Search Optimization

Approach 3: Sorting + Prefix Sum + Binary Search

Approach 4: Sorting + Offline Query + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Longest Subsequence With Limited Sum solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach with Sorting and Prefix Sum

Approach 2: Binary Search Optimization

Approach 3: Sorting + Prefix Sum + Binary Search

Approach 4: Sorting + Offline Query + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems