362. Buy Maximum Stocks if i Stocks Can Be Bought on the i-th Day

Given the price of a stock on each of n days (1-indexed) and a total budget k, where on day i you may buy at most i shares (in total, in any order you like across days), find the maximum number of shares you can buy without exceeding the budget.

Input: The first line contains an integer n, the number of days. The second line contains n space-separated integers, the stock price on each day. The final line contains k, the total budget. Output: Print a single integer - the maximum number of shares that can be bought without exceeding the budget.

1 <= n <= 10^5, 1 <= price <= 10^4, 1 <= k <= 10^9

Each day's per-day purchase limit equals its own DAY NUMBER (day i allows buying at most i shares) - this specific rule needs to be tracked alongside price throughout the sort, not discarded once sorted.

Given a budget and a per-day purchase limit that grows with the day number, buy as many total shares as possible. Brute force: Try every possible combination of how many shares to buy on each day directly, checking budget feasibility - this is combinatorially expensive, when a simple price-sorted greedy directly gives the optimal answer. Optimised: Buying the CHEAPEST available shares first always maximizes the total NUMBER of shares purchasable within a fixed budget - this greedy strategy (process by ascending price, respecting each day's own cap) is provably optimal, since spending the budget on cheaper shares always yields more total shares than spending it on pricier ones.

Model this as choosing, for every day i, how many of its (up to i) shares to buy, subject to the total cost staying within budget k, and search this decision space directly (conceptually a DP over day index and remaining budget). This is correct - it considers every feasible allocation - but the remaining-budget dimension can be as large as 10^9, so it is computationally infeasible at the given constraints even though it is a valid brute-force formulation. Time: O(n*k) Space: O(n*k)

Repeatedly scan the array of (day, price) pairs to find the cheapest day that still has shares left to sell, buy as many shares from it as the budget and its per-day limit allow, mark it exhausted, and repeat until the budget runs out or all days are exhausted. This is correct because always taking the globally cheapest available price first is the greedy strategy that maximizes shares bought, but finding the current cheapest day by re-scanning the whole array every time makes it quadratic instead of exploiting a one-time sort. Time: O(n^2) Space: O(n)

Sort the (day, price) pairs once by ascending price, then walk through them from cheapest to most expensive, buying min(day's max allowed shares, floor(remaining budget / price)) shares at each day and deducting the cost from the budget, stopping once the budget is exhausted. Because buying from the cheapest available price first is always at least as good as any other order (a classic exchange argument), one sort followed by a single linear pass is sufficient and optimal. Time: O(n log n) Space: O(n)

1. Process days in INCREASING order of PRICE (not day number) - buying the cheapest shares available first always leaves the most budget remaining for everything else. 2. On each day (visited in price order), buy as many shares as affordable, capped by BOTH the remaining budget AND that day's own per-day limit (its original day number). 3. Sum up all shares bought this way until the budget runs out or all days are exhausted.

Time: O(n log n), dominated by sorting days by price. Space: O(n), for the sorted (price, day-limit) pairs.

a budget too small to buy even one share on the cheapest day, a budget large enough to buy the maximum allowed shares every day (i shares on day i), and n at its maximum of 10^5 with k up to 10^9 to confirm the price-sorted greedy runs efficiently.

Be ready to explain why sorting by PRICE (not by day number) is the key insight - the per-day LIMIT is just a constraint checked at purchase time, while the PRICE determines the actual greedy processing order.