Buy Maximum Stocks if i stocks can be bought on i-th day

The problem, simply

A stock has a price on each of n days: price[i] on day i + 1. The rule: on day 1 you may buy at most 1 share, on day 2 at most 2 shares, and on day i at most i shares. You start with k money and never get more.

Give back the largest number of shares you can buy. Which days you use does not matter, only how many shares you end up with.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every choice. For each day, try buying 0, 1, up to the limit, as long as the money lasts. Keep the biggest total.

1. Start at day 1 with the full budget.
2. For each amount you could buy today, pay for it and move on to the next day.
3. When the days run out, compare the number of shares with the best so far.

class Solution {
    private long best = 0;

    public long buyMaximumProducts(int[] price, long k) {
        best = 0;
        tryDays(price, 0, k, 0);
        return best;
    }

    private void tryDays(int[] price, int day, long money, long shares) {
        best = Math.max(best, shares);
        if (day == price.length) return;
        int limit = day + 1;                              // day i allows i shares
        for (int buy = 0; buy <= limit; buy++) {
            long cost = (long) buy * price[day];
            if (cost > money) break;                      // cannot afford more today
            tryDays(price, day + 1, money - cost, shares + buy);
        }
    }
}

How long it takes: day i offers i + 1 choices, so there can be 2 * 3 * ... * (n + 1) paths, which is O((n+1)!). Extra room: the recursion, O(n).

Way 2: the clever way

A share is a share. To get the most of them, buy the cheapest ones first.

1. Pair each price with its limit: day i (counting from 1) gives the pair (price, i).
2. Sort the pairs by price, cheapest first.
3. For each pair, buy min(limit, money / price) shares and pay for them.
4. Add up the shares.

Why is this safe? If your plan buys a pricier share while a cheaper offer still has room, swap them. You get the same number of shares and spend less, so you can only gain.

class Solution {
    public long buyMaximumProducts(int[] price, long k) {
        int n = price.length;
        int[][] offers = new int[n][2];
        for (int i = 0; i < n; i++) {
            offers[i][0] = price[i];
            offers[i][1] = i + 1;                 // day i+1 allows i+1 shares
        }
        Arrays.sort(offers, (a, b) -> Integer.compare(a[0], b[0])); // cheapest first

        long shares = 0, money = k;
        for (int[] o : offers) {
            long buy = Math.min(o[1], money / o[0]);   // the limit, or what money allows
            shares += buy;
            money -= buy * o[0];
        }
        return shares;
    }
}

How long it takes: the sort is O(n log n), the walk is O(n). Extra room: the pairs, O(n).

Watch out for

• Day 1 allows 1 share, not 0. With 0 based indexes, the limit is i + 1.
• buy * price can pass the int range. Use long.
• Do not stop at the first offer you cannot fully afford. Buy the part you can afford, then the later, pricier offers buy nothing anyway.

What interviewers ask next

• What if each day allowed any number of shares? Then only the cheapest price matters: answer k / min(price).
• What if you must buy on days in order and can sell too? That is a different family: the stock buy and sell problems with dynamic programming.
• Can you skip the sort? With prices in a small range, bucket them by price and walk the buckets, O(n + maxPrice).
• Why is greedy optimal? Exchange argument: swapping a pricier share for a cheaper one with spare room never lowers the count and never costs more.

Remember this

Grown-up words: the offers are (price, quantity) pairs, buying the cheapest first is a greedy choice, and the swap reasoning is an exchange argument.