GreedyProblem 9 of 35
Buy Maximum Stocks if i stocks can be bought on i-th day
Problem Statement
In a stock market, there is a product with its infinite stocks. The stock prices are given for n days, where price[i] denotes the price of the stock on day i. There is a rule that a customer can buy at most i stocks on the i-th day (1-indexed). Find the maximum number of stocks a customer can buy with an initial amount k.
Constraints:
- 1 ≤ n ≤ 10^5
- 1 ≤ price[i] ≤ 10^6
- 1 ≤ k ≤ 10^9
Example:
- Input:
price = [10, 7, 19],k = 45 - Output:
4 - Explanation: Buy 1 stock on day 1 (cost=10), 2 stocks on day 2 (cost=14). Total = 3 stocks for 24. Or buy 2 stocks on day 2, 1 on day 1. Maximum is 4 stocks.
Example 2:
- Input:
price = [7, 10, 4],k = 100 - Output:
6 - Explanation: Buy 1 on day 1 (7), 2 on day 2 (20), 3 on day 3 (12). Total cost = 39, stocks = 6.
Approach 1: Brute Force (Try All Combinations)
Intuition
Try all possible combinations of how many stocks to buy each day (0 to i stocks on day i) and find the maximum total stocks within budget.
Algorithm
- Use recursion to try buying 0, 1, ..., i stocks on day i
- Track remaining budget and total stocks
- Find maximum stocks achievable
java
public class Solution {
private int maxStocks = 0;
private void solve(int[] price, int day, long budget, int totalStocks) {
maxStocks = Math.max(maxStocks, totalStocks);
if (day >= price.length || budget <= 0) return;
for (int count = 0; count <= day + 1; count++) {
long cost = (long) count * price[day];
if (cost <= budget) {
solve(price, day + 1, budget - cost, totalStocks + count);
}
}
}
public int buyMaxStocks(int[] price, int k) {
maxStocks = 0;
solve(price, 0, k, 0);
return maxStocks;
}
}Complexity Analysis
- Time Complexity: O(n! * n) - Exponential combinations
- Space Complexity: O(n) - Recursion stack
Approach 2: Greedy (Sort by Price, Buy Cheapest First) - Optimal
Intuition
To maximize stocks, buy from days with cheapest prices first. For each day, we can buy at most i stocks, so we need to track both price and the day's limit.
Key Insight: Sort days by price. For each day (in order of price), buy as many stocks as possible within the day's limit and remaining budget.
Algorithm
- Create pairs of (price, day) for each day
- Sort by price ascending
- For each day in sorted order:
- Calculate max stocks we can buy (min of day limit and budget/price)
- Buy those stocks and update budget
- Return total stocks bought
java
import java.util.*;
public class BuyMaxStocks {
public long buyStocks(int[] price, long k) {
int n = price.length;
// Create array: [price, max_stocks_allowed]
int[][] stocks = new int[n][2];
for (int i = 0; i < n; i++) {
stocks[i][0] = price[i];
stocks[i][1] = i + 1;
}
// Sort by price
Arrays.sort(stocks, (a, b) -> a[0] - b[0]);
long totalStocks = 0;
long budget = k;
for (int[] stock : stocks) {
if (budget <= 0) break;
int p = stock[0];
int maxAllowed = stock[1];
long canBuy = Math.min(maxAllowed, budget / p);
totalStocks += canBuy;
budget -= canBuy * p;
}
return totalStocks;
}
public Map<Integer, Long> getPurchasePlan(int[] price, long k) {
int n = price.length;
int[][] stocks = new int[n][3]; // price, maxAllowed, originalDay
for (int i = 0; i < n; i++) {
stocks[i][0] = price[i];
stocks[i][1] = i + 1;
stocks[i][2] = i;
}
Arrays.sort(stocks, (a, b) -> a[0] - b[0]);
Map<Integer, Long> plan = new TreeMap<>();
long budget = k;
for (int[] stock : stocks) {
if (budget <= 0) break;
int p = stock[0];
int maxAllowed = stock[1];
int day = stock[2];
long canBuy = Math.min(maxAllowed, budget / p);
if (canBuy > 0) {
plan.put(day + 1, canBuy);
budget -= canBuy * p;
}
}
return plan;
}
public static void main(String[] args) {
BuyMaxStocks bms = new BuyMaxStocks();
int[] price = {10, 7, 19};
long k = 45;
System.out.println("Maximum stocks: " + bms.buyStocks(price, k));
System.out.println("Purchase plan: " + bms.getPurchasePlan(price, k));
}
}Dry Run Example
price = [10, 7, 19], k = 45
Create stocks array:
(price=10, maxAllowed=1, day=0)
(price=7, maxAllowed=2, day=1)
(price=19, maxAllowed=3, day=2)
After sorting by price:
(price=7, maxAllowed=2, day=1)
(price=10, maxAllowed=1, day=0)
(price=19, maxAllowed=3, day=2)
Processing:
budget = 45, totalStocks = 0
Step 1: price=7, maxAllowed=2
canBuy = min(2, 45/7) = min(2, 6) = 2
totalStocks = 0 + 2 = 2
budget = 45 - 2*7 = 45 - 14 = 31
Step 2: price=10, maxAllowed=1
canBuy = min(1, 31/10) = min(1, 3) = 1
totalStocks = 2 + 1 = 3
budget = 31 - 1*10 = 31 - 10 = 21
Step 3: price=19, maxAllowed=3
canBuy = min(3, 21/19) = min(3, 1) = 1
totalStocks = 3 + 1 = 4
budget = 21 - 1*19 = 21 - 19 = 2
Result: 4 stocks
Purchase plan:
Day 1: 1 stock @ 10 = 10
Day 2: 2 stocks @ 7 = 14
Day 3: 1 stock @ 19 = 19
Total cost: 43, Remaining: 2
Complexity Analysis
- Time Complexity: O(n log n) - Dominated by sorting
- Space Complexity: O(n) - For storing stock-day pairs
Variation: Unlimited Stocks Per Day
If there's no limit on stocks per day:
Key Takeaways
- Greedy by Price: Sort days by price, buy cheapest first
- Day Constraint: Day i allows maximum (i+1) stocks
- Pair Tracking: Track both price and day limit together
- Budget Constraint: At each step, buy min(day_limit, budget/price)
- Sorting Key: Sort by price ascending
- Real Application: Stock market optimization, resource purchasing
- Extension: Can add transaction costs, partial purchases