algoadvance

Leetcode 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. For each query queries[i], find out the maximum length of a subsequence of nums such that the sum of the subsequence is less than or equal to queries[i]. Return an array answer where answer[i] is the answer to the i-th query.

Clarifying Questions

  1. What is the definition of a subsequence?
    • A subsequence is a sequence derived from another sequence by deleting some or none of the elements without changing the order of the remaining elements.
  2. Is it necessary for subsequence elements to be contiguous?
    • No, elements in the subsequence do not need to be contiguous.
  3. Can the elements in nums and queries be negative?
    • No, it is guaranteed that all elements of nums and queries are non-negative integers.
  4. What are the possible lengths of nums and queries?
    • The lengths n and m can be up to 1000.

Strategy

  1. Sort and Prefix Sum:
    • First, sort the nums array.
    • Compute the prefix sum of the sorted nums array. The prefix sum at index i gives the sum of elements from the beginning up to i-th element.
  2. Binary Search:
    • For each query, use binary search on the prefix sum array to quickly find the maximum length of subsequence whose sum is less than or equal to the query value.

Code

import java.util.Arrays;

public class LongestSubsequenceWithLimitedSum {
    public int[] answerQueries(int[] nums, int[] queries) {
        // Sort the nums array
        Arrays.sort(nums);

        // Create a prefix sum array
        int n = nums.length;
        int[] prefixSum = new int[n];
        prefixSum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }

        // Prepare the answer array
        int m = queries.length;
        int[] answer = new int[m];

        // For each query, find the maximum length using binary search
        for (int i = 0; i < m; i++) {
            int query = queries[i];
            int left = 0, right = n - 1;

            // Binary search to find the rightmost position where prefix sum is <= query
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (prefixSum[mid] <= query) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            // The length of the longest subsequence satisfying the condition
            // will be 'right + 1'
            answer[i] = right + 1;
        }

        return answer;
    }

    public static void main(String[] args) {
        LongestSubsequenceWithLimitedSum sol = new LongestSubsequenceWithLimitedSum();
        int[] nums = {4,5,2,1};
        int[] queries = {3, 10, 21};
        int[] results = sol.answerQueries(nums, queries);
        System.out.println(Arrays.toString(results));  // Output: [2, 3, 4]
    }
}

Time Complexity

Therefore, the overall time complexity is (O(n \log n + n + m \log n)), which simplifies to (O((n + m) \log n)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI