Longest Subsequence With Limited Sum - Practice Coding Problems

Longest Subsequence With Limited Sum - Problem

Array Binary Search Greedy Sorting Prefix Sum Easy

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.

Input & Output

Example 1 — Basic Multiple Queries

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

› Output: [2,3,4]

💡 Note: For query 3: best subsequence is [2,1] with sum=3, count=2. For query 10: best is [4,2,1] or [5,2,1] with sum≤10, count=3. For query 21: all elements [4,5,2,1] sum=12≤21, count=4.

Example 2 — Single Element Array

$ Input: nums = [2], queries = [1,3]

› Output: [0,1]

💡 Note: For query 1: element 2>1, so no elements fit, count=0. For query 3: element 2≤3, so one element fits, count=1.

Example 3 — Small Query Limits

$ Input: nums = [10,20,30], queries = [5,15,25]

› Output: [0,1,1]

💡 Note: For query 5: no elements ≤5, count=0. For query 15: only 10≤15, count=1. For query 25: only 10≤25 (since 10+20=30>25), count=1.

Constraints

1 ≤ nums.length, queries.length ≤ 1000
1 ≤ nums[i], queries[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Given nums array and multiple query limits

Greedy Strategy

Sort and pick smallest elements to maximize count within limit

Multiple Queries

Answer each query efficiently using sorted order

Key Takeaway

🎯 Key Insight: To maximize count with limited sum, always pick the smallest available elements first using greedy strategy

Asked in

a Amazon 12 G Google 8 M Microsoft 6

The key insight is that to maximize the count of elements with a limited sum, we should always pick the smallest elements first. The best approach sorts the array once, builds prefix sums, then uses binary search for each query. Time: O(n log n + m log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum + Binary Search	O(n log n + m log n)	O(n)	Sort nums, compute prefix sums, then use binary search to find maximum valid count for each query
Brute Force - Try All Subsequences	O(m × 2ⁿ × n)	O(1)	Generate all possible subsequences and check which ones fit within each query limit
Greedy - Sort and Pick Smallest	O(n log n + m × n)	O(1)	Sort nums, then greedily pick smallest elements until sum exceeds query limit

Prefix Sum + Binary Search — Algorithm Steps

Sort nums array in ascending order
Compute prefix sum array
For each query, binary search to find largest index where prefix[i] ≤ query
The index + 1 gives us the maximum count of elements

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort & Build Prefix

Sort array and compute cumulative sums

Binary Search

For each query, find largest prefix sum ≤ query limit

Return Index

The index gives maximum count of elements within limit

Code -

solution.c — C

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

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

int* solution(int* nums, int numsSize, int* queries, int queriesSize, int* returnSize) {
    // Sort to enable greedy selection and prefix sum optimization
    qsort(nums, numsSize, sizeof(int), compare);
    
    // Compute prefix sums
    long long* prefixSums = (long long*)malloc((numsSize + 1) * sizeof(long long));
    prefixSums[0] = 0;
    for (int i = 0; i < numsSize; i++) {
        prefixSums[i + 1] = prefixSums[i] + nums[i];
    }
    
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int q = 0; q < queriesSize; q++) {
        int query = queries[q];
        
        // Binary search for largest prefix sum <= query
        int left = 0, right = numsSize;
        int ans = 0;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (prefixSums[mid] <= query) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        result[q] = ans;
    }
    
    free(prefixSums);
    return result;
}

int main() {
    // Simple parsing for demo
    int nums[] = {4, 5, 2, 1};
    int queries[] = {3, 10, 21};
    int numsSize = 4;
    int queriesSize = 3;
    int returnSize;
    
    int* result = solution(nums, numsSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m log n)

Sorting takes O(n log n), then each of m queries uses O(log n) binary search

⚡ Linearithmic

Space Complexity

O(n)

Extra space needed for prefix sum array of size n

⚡ Linearithmic Space

26.8K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum + Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler