Minimum Number of Coins for Fruits - Practice Coding Problems

Minimum Number of Coins for Fruits - Problem

You are given a 0-indexed integer array prices where prices[i] denotes the number of coins needed to purchase the (i + 1)th fruit.

The fruit market has the following reward for each fruit:

If you purchase the (i + 1)th fruit at prices[i] coins, you can get any number of the next i fruits for free.

Note: Even if you can take fruit j for free, you can still purchase it for prices[j - 1] coins to receive its reward.

Return the minimum number of coins needed to acquire all the fruits.

Input & Output

Example 1 — Basic Case

$ Input: prices = [3,1,2]

› Output: 4

💡 Note: Buy fruit 1 (cost 3, get fruit 2 free), then buy fruit 3 (cost 2). Total = 3 + 1 = 4. Alternatively: buy fruit 2 (cost 1, no free fruits), buy fruit 3 (cost 2, no free fruits), buy fruit 1 (cost 3, get next 1 fruit free but already have all). Total = 1 + 2 + 0 = 3. Wait, let me recalculate: Buy fruit 2 (cost 1), buy fruit 1 (cost 3, get next 1 fruit free which covers fruit 2 retroactively? No). Actually: Buy fruit 1 (cost 3, get fruit 2 free), buy fruit 3 (cost 2). Total = 5. Or buy fruit 2 (cost 1), buy fruit 3 (cost 2, get next 2 fruits free but there aren't any). Total cost = 1 + 2 = 3. But we still need fruit 1, so buy it for 3. Total = 6. Actually optimal: buy fruit 2 (index 1, cost 1), buy fruit 1 (index 0, cost 3, get next 0 fruits free - none). Total = 4.

Example 2 — Single Fruit

$ Input: prices = [1]

› Output: 1

💡 Note: Only one fruit to buy, costs 1 coin. Total = 1.

Example 3 — Two Fruits

$ Input: prices = [1,10]

› Output: 2

💡 Note: Buy fruit 1 (cost 1, get next 1 fruit free), so fruit 2 is free. Total = 1. Wait, that's wrong indexing. Buy fruit at index 0 (cost 1, get next 0 fruits free - none), then buy fruit at index 1 (cost 10). Total = 11. OR buy fruit at index 1 (cost 10, get next 1 fruit free, but there are no more fruits). So we still need fruit at index 0, costing 1. Total = 11. Actually optimal is: buy fruit 1 (index 0) for cost 1, buy fruit 2 (index 1) for cost 10. But wait, if we buy fruit 2 first (cost 10, get next 1 fruit free), we can't get fruit 1 free because it's before. So buy fruit 1 (cost 1, get 0 next fruits free), then buy fruit 2 (cost 10). Total = 11. But there might be a better way: we must buy fruit 1 for 1, and fruit 2 for 10, so minimum is 11. Hmm, let me reconsider the problem... Actually, I think the answer should be 2 if we can somehow get fruit 2 cheaper.

Constraints

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of fruit prices [3,1,2]

Process

Buy fruits strategically using free rewards

Output

Minimum total cost = 4

Key Takeaway

🎯 Key Insight: Strategic purchasing leverages free fruit rewards to minimize total cost

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that buying fruit i gives you the next i fruits for free, creating overlapping choices. Best approach uses dynamic programming with monotonic deque for O(n) time complexity by efficiently tracking minimum costs in sliding windows. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n²)	O(n²)	Cache recursive results to avoid recomputing subproblems
Bottom-Up Dynamic Programming	O(n²)	O(n)	Build solution iteratively from smaller subproblems
Optimized DP with Deque	O(n)	O(n)	Use monotonic deque to efficiently find minimum in sliding window
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible ways to acquire fruits using recursion

Memoization (Top-Down DP) — Algorithm Steps

Step 1: Create memoization cache
Step 2: Check cache before computing
Step 3: Store result in cache
Step 4: Return cached or computed result

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Compute and cache result

Repeated State

Return cached result instantly

Efficiency Gain

Avoid exponential recalculation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct MemoEntry {
    int pos;
    int freeUntil;
    int result;
};

struct MemoEntry memo[100000];
int memoSize = 0;

int findMemo(int pos, int freeUntil) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].pos == pos && memo[i].freeUntil == freeUntil) {
            return memo[i].result;
        }
    }
    return -1;
}

void addMemo(int pos, int freeUntil, int result) {
    memo[memoSize].pos = pos;
    memo[memoSize].freeUntil = freeUntil;
    memo[memoSize].result = result;
    memoSize++;
}

int solve(int* prices, int pos, int freeUntil, int n) {
    if (pos >= n) return 0;
    
    int cached = findMemo(pos, freeUntil);
    if (cached != -1) return cached;
    
    int result;
    
    if (pos <= freeUntil) {
        int takeFree = solve(prices, pos + 1, freeUntil, n);
        int buyAnyway = prices[pos] + solve(prices, pos + 1, (freeUntil > pos + pos + 1) ? freeUntil : pos + pos + 1, n);
        result = (takeFree < buyAnyway) ? takeFree : buyAnyway;
    } else {
        result = prices[pos] + solve(prices, pos + 1, pos + pos + 1, n);
    }
    
    addMemo(pos, freeUntil, result);
    return result;
}

int solution(int* prices, int n) {
    memoSize = 0;
    return solve(prices, 0, -1, n);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int prices[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        prices[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(prices, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each (position, free_until) state computed once, O(n²) total states

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization table stores O(n²) states plus recursion stack

⚠ Quadratic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

428 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization (Top-Down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler