LeetCode Entry

2389. Longest Subsequence With Limited Sum

25.12.2022 easy 2022 kotlin

fun answerQueries(nums: IntArray, queries: IntArray): IntArray {

2389. Longest Subsequence With Limited Sum easy

https://t.me/leetcode_daily_unstoppable/63

blog post

    fun answerQueries(nums: IntArray, queries: IntArray): IntArray {
       nums.sort()
       for (i in 1..nums.lastIndex) nums[i] += nums[i-1]
       return IntArray(queries.size) {
           val ind = nums.binarySearch(queries[it])
           if (ind < 0) -ind-1 else ind+1
       }
    }

We can logically deduce that for the maximum number of arguments we need to take as much as possible items from the smallest to the largest. We can sort items. Then pre-compute sums[i] = sum from [0..i]. Then use binary search target sum in sums. Also, can modify nums but that’s may be not necessary.

Space: O(N), Time: O(NlogN)