Skip to main content
Talentd

Longest Subsequence With Limited Sum - Solution & Explanation

EasyArrayBinary SearchGreedySorting27 min readAsked at: Amazon, Meta, Uber +1
Practice this problem

Problem Statement

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] <= 106

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.

This C solution first sorts the nums array. Then, it computes the prefix sums, allowing us to easily check how many elements from the start can be summed without exceeding the query value. The output is prepared as an array of maximum sizes of these subsequences.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n + m * 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.

This C code implements binary search on the prefix sum array to quickly determine how many elements from the sorted array have a sum that fits within the query limit. This is more efficient than iterating linearly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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 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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Sorting and Prefix Sum

Time Complexity: O(n log n + m * 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(n) for the prefix sum array.

Sorting + Prefix Sum + Binary Search—
Sorting + Offline Query + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 SearchO(n log n + q log n)O(n)Best for large query counts; efficient lookups using sorted prefix sums

Video Solution

Longest Subsequence With Limited Sum : Explanation ➕ Live Coding👩🏻‍💻🧑🏻‍💻🤯😱 • codestorywithMIK • 7,161 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Longest Subsequence With Limited Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

How Many Numbers Are Smaller Than the Current Number

Next

Successful Pairs of Spells and Potions