Skip to main content
Talentd

Maximize Total Tastiness of Purchased Fruits - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDynamic Programming9 min readAsked at: LinkedIn
Practice this problem

Problem Statement

You are given two non-negative integer arrays price and tastiness, both arrays have the same length n. You are also given two non-negative integers maxAmount and maxCoupons.

For every integer i in range [0, n - 1]:

  • price[i] describes the price of ith fruit.
  • tastiness[i] describes the tastiness of ith fruit.

You want to purchase some fruits such that total tastiness is maximized and the total price does not exceed maxAmount.

Additionally, you can use a coupon to purchase fruit for half of its price (rounded down to the closest integer). You can use at most maxCoupons of such coupons.

Return the maximum total tastiness that can be purchased.

Note that:

  • You can purchase each fruit at most once.
  • You can use coupons on some fruit at most once.

 

Example 1:

Input: price = [10,20,20], tastiness = [5,8,8], maxAmount = 20, maxCoupons = 1
Output: 13
Explanation: It is possible to make total tastiness 13 in following way:
- Buy first fruit without coupon, so that total price = 0 + 10 and total tastiness = 0 + 5.
- Buy second fruit with coupon, so that total price = 10 + 10 and total tastiness = 5 + 8.
- Do not buy third fruit, so that total price = 20 and total tastiness = 13.
It can be proven that 13 is the maximum total tastiness that can be obtained.

Example 2:

Input: price = [10,15,7], tastiness = [5,8,20], maxAmount = 10, maxCoupons = 2
Output: 28
Explanation: It is possible to make total tastiness 20 in following way:
- Do not buy first fruit, so that total price = 0 and total tastiness = 0.
- Buy second fruit with coupon, so that total price = 0 + 7 and total tastiness = 0 + 8.
- Buy third fruit with coupon, so that total price = 7 + 3 and total tastiness = 8 + 20.
It can be proven that 28 is the maximum total tastiness that can be obtained.

 

Constraints:

  • n == price.length == tastiness.length
  • 1 <= n <= 100
  • 0 <= price[i], tastiness[i], maxAmount <= 1000
  • 0 <= maxCoupons <= 5

Approach Overview

Problem Overview: You are given arrays price and tastiness. Each fruit can be purchased normally or with a coupon that halves its price. With a fixed budget and limited coupons, the goal is to maximize the total tastiness of the fruits you buy.

Approach 1: Brute Force Recursion (Exponential Time, O(2^n) time, O(n) space)

Try every decision for each fruit: skip it, buy it at full price, or buy it using a coupon. The recursion explores all combinations while tracking remaining budget and coupons. This guarantees the optimal result but quickly becomes impractical because the number of states grows exponentially. It mainly helps understand the decision structure before applying dynamic programming.

Approach 2: Memoization Search (Top-Down DP) (O(n * amount * coupons) time, O(n * amount * coupons) space)

Cache the recursive states to avoid recomputation. The state can be represented as dfs(i, remainingAmount, remainingCoupons), meaning the maximum tastiness achievable starting from fruit i with the given budget and coupons left. For each fruit, consider three options: skip it, buy it at full price if affordable, or buy it using a coupon if coupons remain. Store results in a memo table so repeated states return instantly. This converts the exponential search into a manageable DP solution. The technique is a classic combination of dynamic programming and array traversal.

Approach 3: Bottom-Up Knapsack DP (O(n * amount * coupons) time, O(n * amount * coupons) space)

This problem can also be modeled as a 3D knapsack-style DP. Build a table where dp[i][a][c] represents the best tastiness using the first i fruits with budget a and c coupons. Transition by skipping the fruit, buying it normally, or buying it with a coupon. While the complexity matches the memoized version, the iterative formulation is sometimes easier to reason about for knapsack-style interview problems.

Recommended for interviews: The memoized DFS solution is usually the clearest. It directly models the decision tree and demonstrates strong understanding of dynamic programming state design. Explaining the brute-force recursion first shows you understand the search space, while the memoized version shows optimization skills expected in a medium-level interview problem.

Solution

We design a function dfs(i, j, k) to represent the maximum total tastiness starting from the ith fruit, with j money left, and k coupons left.

For the ith fruit, we can choose to buy or not to buy. If we choose to buy, we can decide whether to use a coupon or not.

If we don't buy, the maximum total tastiness is dfs(i + 1, j, k);

If we buy, and choose not to use a coupon (requires j\ge price[i]), the maximum total tastiness is dfs(i + 1, j - price[i], k) + tastiness[i]; if we use a coupon (requires k\gt 0 and j\ge \lfloor \frac{price[i]}{2} \rfloor), the maximum total tastiness is dfs(i + 1, j - \lfloor \frac{price[i]}{2} \rfloor, k - 1) + tastiness[i].

The final answer is dfs(0, maxAmount, maxCoupons).

The time complexity is O(n times maxAmount times maxCoupons), where n is the number of fruits.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force RecursionO(2^n)O(n)Conceptual baseline to understand all purchase choices
Memoization Search (Top-Down DP)O(n * amount * coupons)O(n * amount * coupons)General optimal solution; avoids recomputation with cached states
Bottom-Up Knapsack DPO(n * amount * coupons)O(n * amount * coupons)When you prefer iterative DP tables over recursion

Video Solution

2431. Maximize Total Tastiness of Purchased Fruits (Leetcode Medium) • Programming Live with Larry • 283 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Maximize Total Tastiness of Purchased Fruits easy or hard?
The problem is rated Medium on LeetCode. The difficulty comes from defining the correct DP state and handling two constraints simultaneously: remaining budget and remaining coupons. Once the state transition is clear, the solution follows a standard memoized dynamic programming pattern.
Maximize Total Tastiness of Purchased Fruits Python/Java solution
Most implementations use a recursive DFS with memoization. Python typically uses functools.lru_cache or a dictionary for caching, while Java uses a HashMap or a 3D DP array. Both implementations achieve O(n * amount * coupons) time complexity.
What is the best approach for Maximize Total Tastiness of Purchased Fruits?
The most practical approach is memoized dynamic programming. Define a state (index, remaining budget, remaining coupons) and compute the maximum tastiness using DFS with caching. This reduces the exponential search to O(n * amount * coupons) time by avoiding repeated subproblems.
Is Maximize Total Tastiness of Purchased Fruits asked at Google/Amazon/Meta?
Problems with similar patterns frequently appear in interviews at companies like Amazon, Google, and Meta. The question combines knapsack-style dynamic programming with an additional resource constraint (coupons), which is a common interview variation.
What data structure is used in Maximize Total Tastiness of Purchased Fruits?
The main technique uses dynamic programming with memoization, typically implemented with a hash map or multidimensional array for caching states. Arrays store the price and tastiness values, while the DP structure stores computed results for each state.
What is the time complexity of Maximize Total Tastiness of Purchased Fruits?
The optimized dynamic programming solution runs in O(n * amount * coupons) time. Each state defined by fruit index, remaining budget, and remaining coupons is computed once and stored in a memo table. Space complexity is also O(n * amount * coupons) due to memoization.
How to solve Maximize Total Tastiness of Purchased Fruits in O(n * amount * coupons)?
Use a top‑down DFS with memoization. For each fruit, evaluate three choices: skip it, buy it with full price, or buy it with a coupon that halves the price. Cache results for the state (i, remainingAmount, remainingCoupons) so the recursion never recomputes the same scenario.

Ready to solve this problem?

Practice Maximize Total Tastiness of Purchased Fruits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays