Solution: Longest Subsequence With Limited Sum

Let’s solve the Longest Subsequence With Limited Sum problem using the Sort and Search pattern.

We'll cover the following

Statement

You are given an integer array, nums, of length n, and an integer array, queries, of length m.

For each element in queries, determine the maximum number of elements that can be selected from nums to form a subsequenceA subsequence is formed by removing zero or more elements from the array without changing the order of the remaining elements. such that the sum of the selected elements is less than or equal to the query value.

Return an array answer of length m, where answer[i] represents the size of the largest subsequence of nums whose sum is less than or equal to queries[i].

Constraints

  • n ==== nums.length

  • m ==== queries.length

  • 1≤1 \leq n, m ≤103\leq 10^3

  • 1≤1 \leq nums[i], queries[i] ≤105\leq 10^5

Solution

The algorithm begins by sorting the nums array in ascending order to facilitate efficient binary search operations. It then constructs a prefix sum array, where each element represents the cumulative sum of elements in nums up to that index. This allows quick and efficient calculation of the sum of any contiguous subsequence.

For each query, the algorithm uses a binary search on the prefix sum array to determine the maximum length of a subsequence whose sum is less than or equal to the query value. The binary search identifies the largest index where the cumulative sum does not exceed the query. All elements from the start of the array up to this index form the valid subsequence, and the index corresponds directly to its length.

The algorithm steps are as follows:

  1. Sort the nums array in ascending order to ensure that smaller elements are considered first when constructing subsequences. This helps us form subsequences with minimal sums, making it easier to find valid subsequences for each query.

  2. Construct a prefixSum array, where each element represents the cumulative sum of elements in nums up to that index. This allows quick calculation of the sum for any contiguous subsequence.

  3. For each query, perform a binary search on the prefixSum array to find the maximum number of elements in nums whose sum does not exceed the query value. The binary search works as follows:

    1. Initialize two pointers: low at the start of the array and high at the end.

    2. Iterate while low <= high:

      1. Compute the midpoint: mid = (low + high) / 2.

      2. If prefixSum[mid] <= query, it indicates that a subsequence ending at mid is valid. Update low to mid + 1 to explore larger subsequences.

      3. Otherwise, update high to mid - 1 to search for smaller subsequences.

  4. After the binary search, the low pointer indicates the largest valid subsequence length. All elements from the start of the array up to low - 1 form this subsequence, as their cumulative sum is less than or equal to the query value.

  5. Append the value of low (representing the subsequence length) to the answer list.

  6. After processing all queries, the answer list contains the lengths of the largest subsequences for each query. Return this answer list.

Let’s look at the following illustration to get a better understanding of the solution:

Press + to interact
canvasAnimation-image
1 of 20

Let’s look at the code for the algorithm we just discussed.

import java.util.*;
public class Solution {
    public static int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int[] prefixSum = new int[nums.length];
        prefixSum[0] = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int q = queries[i];
            int index = binarySearch(prefixSum, q);
            answer[i] = index;
        }
        return answer;
    }
    public static int binarySearch(int[] prefixSum, int target) {
        int low = 0, high = prefixSum.length - 1;
        
        while (low <= high) {
            int mid = (low + high) / 2;
            if (prefixSum[mid] <= target) {
                low = mid + 1;  
            } else {
                high = mid - 1;  
            }
        }
        return low;  
    }
    public static void main(String[] args) {
        int[][] numsList = {
            {4, 5, 2, 1},
            {2, 3, 4, 5},
            {1, 2, 3, 4, 5},
            {10, 20, 30},
            {7, 3, 9, 2}
        };
        int[][] queriesList = {
            {3, 10, 21},
            {1},
            {10, 15, 5},
            {25, 50, 5},
            {5, 10, 20}
        };
        for (int i = 0; i < numsList.length; i++) {
            int[] nums = numsList[i];
            int[] queries = queriesList[i];
            int[] result = answerQueries(nums, queries);
            System.out.println((i + 1) + ".\tnums: " + Arrays.toString(nums));
            System.out.println("\tqueries: " + Arrays.toString(queries));
            System.out.println("\n\tResult: " + Arrays.toString(result));
            System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Longest Subsequence With Limited Sum

Time complexity

Sorting an array takes O(nlog⁡n)O(n \log n), where nn is the number of elements in nums. Constructing prefixSum takes O(n)O(n). For each query, the binary search on the prefixSum array takes O(log⁡n)O(\log n), as it performs a standard binary search on a sorted array. Since there are m queries, the total time for the binary search is O(mlog⁡n)O(m \log n).

The sorting step and the binary search for all queries will dominate the time complexity. Thus, the total time complexity is O(nlog⁡n+mlog⁡n)O(n \log n+m \log n), which simplifies to O((n+m)log⁡n)O((n+m)\log n).

Space complexity

This prefixSum array stores the prefix sums and its size is equal to the size of the nums array, so it takes O(n)O(n) space.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.