2389. Longest Subsequence With Limited Sum

Hello, reader 👋🏽 ! Welcome to day 85 of the series on Problem Solving. Through this series, I aim to pick up at least one question every day and share my approach to solving it.

Today, I will be picking up LeetCode's daily challenge problem: 2389. Longest Subsequence With Limited Sum.

🤔 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.
E.g.:
- nums = [4,5,2,1], queries = [3,10,21] => [2,3,4]
- nums = [2,3,4,5], queries = [1] => [0]

💬 Thought Process - Sort and Simulate

We will iterate through every query in queries array and try to find the maximum subsequence size with a sum less than or equal to them.
The best way to find the maximum subsequence is to calculate the sum from the smallest number until sum <= query is violated.
Hence, we would sort the numbers and for every query, we will start calculating the sum from the first number.

👩🏽‍💻 Solution - Sort and Simulate

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        int m = queries.length, n = nums.length;
        int[] maxSizes = new int[m];
        Arrays.sort(nums);

        for(int i = 0; i < m; i++) {
            int query = queries[i];
            int sum = 0;
            int j = 0;
            while(j < n) {
                sum += nums[j];
                if(sum > query) {
                    break;
                }
                j++;
            }

            maxSizes[i] = j;
        }


        return maxSizes;
    }
}

Time Complexity: O(n*m + n*log n)
Space Complexity: O(n) or (log n)
    - aux space used for sorting

💬 Thought Process - Prefix Sum and Binary Search

We can avoid O(m*n) time complexity by calculating the prefix sum of sorted numbers.
Then for every query, we can perform a binary search on the prefix sum calculated.
If we found the exact query sum, then we will return the mid index.
Else, we return the floor for the query, which would be at the index end.
If the answer was not found at all, we will return 0.

👩🏽‍💻 Solution - Prefix Sum and Binary Search

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        int m = queries.length, n = nums.length;

        int[] maxSizes = new int[m];
        int[] prefixSum = new int[n];
        Arrays.sort(nums);

        prefixSum[0] = nums[0];
        for(int i = 1; i < n; i++) {
            int num = nums[i];
            prefixSum[i] = nums[i] + prefixSum[i-1];
        }

        for(int i = 0; i < m; i++) {
            int query = queries[i];

            int maxSize = binarySearch(prefixSum, query);
            maxSizes[i] = maxSize;
        }

        return maxSizes;
    }

    private int binarySearch(int[] nums, int target) {
        int n = nums.length;
        int start = 0, end = n-1;
        int answer = -1;

        while(start <= end) {
            int mid = start + (end - start)/2;
            if(nums[mid] == target) {
                return mid + 1;
            }
            if(nums[mid] > target) {
                end = mid - 1;
            }
            else {
                answer = mid;
                start = mid + 1;
            }
        }
        if(answer == -1) return 0;

        return end + 1;
    }
}

Time Complexity: O(n*log n + n*log n)
Space Complexity: O(n)
    - extra space used in prefix sum

You can find the link to all the solutions on GitHub for this question here: 790. Domino and Tromino Tiling.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian