Most Items Within Budget from a Start Index
Updated
Problem statement
A store has n items in a row. prices[i] is the price of item i, and indices start at 0.
Each query is a pair [start, budget]. For that query, you may buy only items whose index is at least start. Each item can be bought at most once, and the total price of the items you buy must not be more than budget. The items you buy do not have to be next to each other.
For each query, find the largest number of items you can buy. The queries do not affect each other: every query starts with all items available. Return the answers in the same order as queries.
Function
maxItems(prices: int[], queries: int[][]) → int[]Examples
Example 1
prices = [4,2,7,1,3]queries = [[0,6],[2,4],[1,10],[4,2]]return = [3,2,3,0]Query [0, 6]: all five items are allowed. Buy the cheapest first: 1 + 2 + 3 = 6, which uses the whole budget, so the answer is 3.
Query [2, 4]: only indices 2, 3 and 4 are allowed, with prices 7, 1 and 3. 1 + 3 = 4 fits, so the answer is 2.
Query [1, 10]: the allowed prices are 2, 7, 1 and 3. 1 + 2 + 3 = 6 fits, but adding 7 would make 13, which is more than 10. The answer is 3.
Query [4, 2]: only the item with price 3 is allowed, and it costs more than 2. The answer is 0.
Example 2
prices = [5,5,5]queries = [[0,0],[0,15],[1,14],[2,5]]return = [0,3,2,1]With a budget of 0, nothing can be bought. With a budget of 15, all three items fit, because 5 + 5 + 5 = 15.
Query [1, 14] allows two items, and 5 + 5 = 10 fits. Query [2, 5] allows one item, and it costs exactly 5.
Example 3
prices = [8,1,1,1,9]queries = [[0,9],[0,11],[1,2]]return = [3,4,2]Query [0, 9]: buying from left to right would take 8 and then 1, only 2 items. Buying the cheapest first takes 1 + 1 + 1 = 3. The next cheapest costs 8, and 3 + 8 = 11 is more than 9, so the answer is 3.
Query [0, 11]: 1 + 1 + 1 + 8 = 11 uses the budget exactly, so the answer is 4.
Query [1, 2]: the allowed prices are 1, 1, 1 and 9. Two items cost 1 + 1 = 2, so the answer is 2.
Constraints
1 <= prices.length <= 10^51 <= prices[i] <= 10^91 <= queries.length <= 10^5queries[j].length == 20 <= queries[j][0] < prices.length0 <= queries[j][1] <= 10^9
More Hudson River Trading Online Assessment questions
- Count Palindrome Addition ChoicesOA · Seen Nov 2026
- Count Multiples of Three with Two SevensOA · Seen Oct 2026
- Recursively Expanded Shell Command CountsOA · Seen Oct 2026
- Rotate Matrix Regions Around the DiagonalsOA · Seen Oct 2026
- Maximum Diamond SumOA · Seen Oct 2026
- Smallest Most-Lit Street PositionOA · Seen Oct 2026
- Rearrange String by Alternating EndsOA · Seen Sep 2026
- Count Sawtooth SubarraysOA · Seen Aug 2026
- Backtick Identifier ConverterOA · Seen Jun 2026
- Max Minus Min Weight in Every SubtreeOA · Seen Sep 2025
Similar questions at other companies
- Minimum Swaps to Sort a Ternary Array After UpdatesGoogle · OAGoogle interview questions
- Rebuild the Queue From Taller-in-Front CountsAdobe · PHONE SCREENAdobe interview questions
- Maximize K-Element AND with an Increment BudgetAmazon · OA
- Delete and Freeze GameRubrik · OARubrik interview questions
- Most Segments That Sort the ArrayRippling · OARippling interview questions
- Luna and the Colorful SocksPhonePe · OAPhonePe interview questions
- Minimum Starting Coins to Buy All ProductsMicrosoft · OAMicrosoft interview questions
- Get Max EfficiencySalesforce · OASalesforce interview questions
- Finding a Hidden Benchmark ValueSamsung · OASamsung interview questions
- Catch Fish with Reusable BaitsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions