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!