In this guide, you will get 879. Profitable Schemes LeetCode Solution with the best time and space complexity. The solution to Profitable Schemes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can’t participate in another crime.
Let’s call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n.
Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.
Example 2:
Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: To make a profit of at least 5, the group could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).
Time Complexity: O(gnp), where g = |\texttt{group}| and p = \texttt{minProfit}
Space Complexity: O(gnp), where g = |\texttt{group}| and p = \texttt{minProfit}
879. Profitable Schemes LeetCode Solution in C++
class Solution {
public:
int profitableSchemes(int n, int minProfit, vector<int>& group,
vector<int>& profit) {
constexpr int kMod = 1'000'000'007;
// dp[k][i][j] := the number of schemes, where the first k crimes are
// committed by <= i members, generating >= j profits
vector<vector<vector<int>>> dp(
group.size() + 1,
vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
// No crimes, no profits, and any number of members.
for (int i = 0; i <= n; ++i)
dp[0][i][0] = 1;
for (int k = 1; k <= group.size(); ++k) {
const int g = group[k - 1];
const int p = profit[k - 1];
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= minProfit; ++j)
if (i < g) {
dp[k][i][j] = dp[k - 1][i][j];
} else {
dp[k][i][j] = dp[k - 1][i][j] + dp[k - 1][i - g][max(0, j - p)];
dp[k][i][j] %= kMod;
}
}
return dp[group.size()][n][minProfit];
}
}; /* code provided by PROGIEZ */
879. Profitable Schemes LeetCode Solution in Java
class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
final int kMod = 1_000_000_007;
// dp[k][i][j] := the number of schemes, where the first k crimes are
// committed by <= i members, generating >= j profits
int[][][] dp = new int[group.length + 1][n + 1][minProfit + 1];
// No crimes, no profits, and any number of members.
for (int i = 0; i <= n; ++i)
dp[0][i][0] = 1;
for (int k = 1; k <= group.length; ++k) {
final int g = group[k - 1];
final int p = profit[k - 1];
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= minProfit; ++j)
if (i < g) {
dp[k][i][j] = dp[k - 1][i][j];
} else {
dp[k][i][j] = dp[k - 1][i][j] + dp[k - 1][i - g][Math.max(0, j - p)];
dp[k][i][j] %= kMod;
}
}
return dp[group.length][n][minProfit];
}
} // code provided by PROGIEZ
879. Profitable Schemes LeetCode Solution in Python
class Solution {
public:
int profitableSchemes(int n, int minProfit, vector<int>& group,
vector<int>& profit) {
constexpr int kMod = 1'000'000'007;
// dp[i][j] := the number of schemes, where <= i members, generating
// >= j profits
vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
for (int i = 0; i <= n; ++i)
dp[i][0] = 1;
for (int k = 1; k <= group.size(); ++k) {
const int g = group[k - 1];
const int p = profit[k - 1];
for (int i = n; i >= g; --i)
for (int j = minProfit; j >= 0; --j) {
dp[i][j] += dp[i - g][max(0, j - p)];
dp[i][j] %= kMod;
}
}
return dp[n][minProfit];
}
}; # code by PROGIEZ
