Purchase Optimization

Problem

Alex is shopping at a mall with n cubicles arranged in a row. Each cubicle sells exactly one item; prices[i] is the price at cubicle i + 1 (1-indexed). The price array is non-decreasing, so cubicles farther down the row never undercut earlier ones. Alex can buy at most one item per cubicle.

You are given q queries as parallel arrays pos and amount. For query j, Alex starts at cubicle pos[j] and walks toward cubicle n, visiting every cubicle in order. Within a budget of amount[j], return the maximum number of items Alex can buy. The answer for each query should be returned as the j-th entry in the output array.

Requirements

1. Process every query independently. The starting cubicle pos[j] is 1-indexed and inclusive.
2. Buy items greedily: because prices are non-decreasing, the cheapest reachable items are the earliest ones in the suffix.
3. Use prefix sums + binary search so each query runs in O(log n) instead of O(n).

Constraints

• 1 <= n, q <= 10^5
• 1 <= prices[i] <= 10^4, non-decreasing
• 1 <= pos[j] <= n
• 0 <= amount[j] <= 10^9

Examples

Example 1:

Input: prices = [3, 4, 5, 5, 7], pos = [2, 1, 5], amount = [10, 24, 5] Output: [2, 5, 0]

Example 2:

Input: prices = [2, 2, 2, 2, 2], pos = [3], amount = [4] Output: [2]

Example 3:

Input: prices = [1, 1, 1, 100], pos = [4], amount = [50] Output: [0]

Hint 1: Why greed works here Because the price array is non-decreasing, every suffix prices[start:] is also non-decreasing. To maximize the number of items within a budget, you always want the cheapest available items — which are the earliest in that suffix. So the answer for a query is the largest k such that prices[start] + prices[start+1] + ... + prices[start + k - 1] <= budget.

Hint 2: Prefix sums turn it into binary search Precompute prefix[i] = prices[0] + ... + prices[i-1] once in O(n). Then the cost of buying k items starting at index start is prefix[start + k] - prefix[start]. For each query, binary search the largest k with prefix[start + k] - prefix[start] <= budget.

Full Solution ` from bisect import bisect_right

def maxItems(prices, pos, amount): n = len(prices) prefix = [0] * (n + 1) for i in range(n): prefix[i + 1] = prefix[i] + prices[i]

out = []
for p, budget in zip(pos, amount):
    start = p - 1
    # Largest k such that prefix[start + k] - prefix[start] <= budget.
    # Binary search on the suffix [prefix[start], ..., prefix[n]] for
    # the rightmost value <= prefix[start] + budget.
    target = prefix[start] + budget
    # bisect_right gives insertion index for target+1. We want largest idx
    # with prefix[idx] <= target.
    idx = bisect_right(prefix, target, start, n + 1) - 1
    out.append(idx - start)
return out

`

Approach:

1. Prefix sums in one pass produces prefix[0..n] so any range sum is prefix[r] - prefix[l].
2. Per-query binary search finds the largest index idx >= start with prefix[idx] <= prefix[start] + budget. The number of items bought is idx - start.
3. Bounded bisect_right. Restrict the search to [start, n + 1) so we never accidentally pick an idx < start (which would correspond to "buying nothing from a cubicle before the start").

Time Complexity: O(n + q log n) — O(n) to build the prefix array, O(log n) per query.

Space Complexity: O(n) for the prefix-sum array, O(q) for the output.