LeetCode 2389: Longest Subsequence With Limited Sum Solution

Master LeetCode problem 2389 (Longest Subsequence With Limited Sum), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2389. Longest Subsequence With Limited Sum

Easy

Array Binary Search Greedy Sorting Prefix Sum

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will iterate through each query and for each query, we will iterate through the nums array to find the maximum size of subsequence with sum less than or equal to the query limit. We will keep track of the maximum size for each query and return the results.

Sort the nums array to optimize the process.
Initialize an array to store the maximum sizes for each query.
Iterate through each query and for each query, iterate through the sorted nums array to find the maximum size of subsequence.
Use dynamic programming to keep track of the maximum size.

Time complexity: O(n * m * log(n)) where n is the length of nums array and m is the length of queries array. Space complexity: O(n) where n is the length of nums array.

Solution Code

import java.util.Arrays;

class Solution {
    public int[] maxSubsequenceSizes(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int[] result = new int[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int sum = 0;
            int size = 0;
            for (int j = 0; j < nums.length; j++) {
                sum += nums[j];
                if (sum <= queries[i]) {
                    size++;
                } else {
                    break;
                }
            }
            result[i] = size;
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2389 (Longest Subsequence With Limited Sum)?

This page provides optimized solutions for LeetCode problem 2389 (Longest Subsequence With Limited Sum) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2389 (Longest Subsequence With Limited Sum)?

The time complexity for LeetCode 2389 (Longest Subsequence With Limited Sum) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2389 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2389 in Java, C++, or Python.

Back to LeetCode Solutions