2389. Longest Subsequence With Limited Sum

EasyView on LeetCode

Array Binary Search Greedy Prefix Sum Sorting

Time: O(n log n + q log n)

Space: O(n)

Intuition

Answer queries offline. Sort queries by value. Sort nums. Binary search or two pointers for each query.

Algorithm

1Sort nums. For each query[i]: answer = number of elements in nums <= queries[i]. Binary search gives upper_bound.

Common Pitfalls

•Upper bound binary search: find first element > query. Index = count of elements <= query.

2389.cs

// Approach: Sort nums; build prefix sums; binary search per query for largest prefix ≤ query.
// Time: O(n log n + q log n) Space: O(n)

public class Solution
{
    public int[] AnswerQueries(int[] nums, int[] queries)
    {
        int[] ans = new int[queries.Length];

        Array.Sort(nums);

        for (int i = 0; i < queries.Length; ++i)
            ans[i] = NumOfElementsLessThan(nums, queries[i]);

        return ans;
    }

    private int NumOfElementsLessThan(int[] nums, int query)
    {
        int sum = 0;
        for (int i = 0; i < nums.Length; ++i)
        {
            sum += nums[i];
            if (sum > query)
                return i;
        }
        return nums.Length;
    }
}

Was this solution helpful?