879. Profitable Schemes Solution

Q: Is Profitable Schemes easy or hard?

Profitable Schemes is classified as Hard on LeetCode. The challenge comes from modeling the problem as a constrained knapsack counting problem and managing the additional profit dimension efficiently with dynamic programming.

Q: Profitable Schemes Python/Java solution

Implement the space-optimized dynamic programming approach. Use a 2D array dp[g][p] where g is the number of members used and p is profit capped at minProfit. Update the table for each crime in reverse group order and apply modulo 1e9+7 after every addition.

Q: How to solve Profitable Schemes in O(n)?

Pure O(n) time is not achievable because both group size and profit must be tracked. The optimal approach uses dynamic programming with complexity O(m * n * minProfit). Space can be reduced to O(n * minProfit) using state compression while maintaining the same time complexity.

Q: What is the best approach for Profitable Schemes?

The best approach is dynamic programming using a 2D DP table that tracks group size and accumulated profit. For each crime, update states in reverse order of members and cap profit at minProfit. This runs in O(m * n * minProfit) time with O(n * minProfit) space, which fits the problem constraints.

Q: Is Profitable Schemes asked at Google/Amazon/Meta?

Dynamic programming problems similar to Profitable Schemes appear frequently in interviews at companies like Amazon, Google, and Meta. The pattern resembles 0/1 knapsack counting problems with additional constraints, which are common in system and algorithm interviews.

Q: What data structure is used in Profitable Schemes?

The primary data structure is a dynamic programming table (2D array) indexed by group size and profit. The input itself is stored in arrays representing the number of members required and profit generated for each crime.

Q: What is the time complexity of Profitable Schemes?

The optimal dynamic programming solution runs in O(m * n * minProfit) time, where m is the number of crimes, n is the maximum group size, and minProfit is the profit threshold. Each crime updates all combinations of group size and profit states once.

The problem

There is a group of n members, and a list of various crimes they could commit. The i^th 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 10⁹ + 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).

Constraints:

1 <= n <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100

Approach overview

Problem Overview: You are given a set of crimes where each crime requires a certain number of members and generates some profit. With at most n members available, count how many subsets of crimes generate at least minProfit. Each crime can be chosen once, and the answer must be returned modulo 1e9 + 7.

Approach 1: Brute Force Subset Enumeration (Time: O(2^m), Space: O(m))

The most direct idea is to generate every subset of crimes and check whether it satisfies both constraints: total members used ≤ n and total profit ≥ minProfit. You iterate through all 2^m subsets, accumulate the group size and profit for each, and count valid schemes. This approach demonstrates the core combinatorial nature of the problem but quickly becomes infeasible when m grows (up to 100). The exponential complexity makes it unsuitable for real inputs.

Approach 2: 3D Dynamic Programming (Time: O(m * n * minProfit), Space: O(m * n * minProfit))

The key observation is that this is a constrained subset counting problem. Define a DP state dp[i][g][p] representing the number of ways to consider the first i crimes, using g members, and achieving profit p. For each crime, you either skip it or include it. When including it, update the member count and clamp profit to minProfit because anything beyond the target is equivalent for counting purposes. This transforms the exponential search into a structured dynamic programming solution over crime index, group size, and profit states. The approach is clear and systematic but consumes significant memory.

Approach 3: Space-Optimized DP (Time: O(m * n * minProfit), Space: O(n * minProfit))

The crime index dimension is unnecessary because each transition depends only on the previous state. Collapse the DP into a 2D table dp[g][p], where g is the number of members used and p is the profit achieved. Iterate through each crime and update the table in reverse order of members to avoid overwriting states needed in the same iteration. Profit is updated as newProfit = min(minProfit, p + profit[i]) so all profits beyond the threshold accumulate in the same bucket. This reduces space significantly while keeping the same time complexity. The technique is common in knapsack-style problems involving arrays and dynamic programming.

Recommended for interviews: The space-optimized DP is the expected solution. Interviewers want to see the recognition that this is a variation of the 0/1 knapsack counting problem with two constraints (members and profit). Mentioning the brute force approach shows you understand the combinatorial search space, but implementing the optimized DP demonstrates strong dynamic programming skills and awareness of state compression techniques.

Approach 1: Dynamic Programming Approach

This approach leverages dynamic programming to efficiently determine the number of profitable schemes. We use a 3D DP array where dp[i][j][k] represents the number of ways to select from the first i crimes such that exactly j members are used and at least k profit is generated. We iterate over each crime and update our DP table based on whether we include the crime or not in our solution set.

Python

def profitableSchemes(n, minProfit, group, profit):
    MOD = 10**9 + 7
    length = len(group)
    dp = [[[0] * (minProfit + 1) for _ in range(n + 1)] for _ in range(length + 1)]
    dp[0][0][0] = 1
    for i in range(1, length + 1):
        g = group[i - 1]
        p = profit[i - 1]
        for j in range(n + 1):
            for k in range(minProfit + 1):
                dp[i][j][k] = dp[i - 1][j][k]
                if j >= g:
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][max(0, k - p)]) % MOD
    return sum(dp[length][j][minProfit] for j in range(n + 1)) % MOD

Java

import java.util.*;

public class ProfitableSchemes {

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        final int MOD = 1_000_000_007;
        int length = group.length;
        int[][][] dp = new int[length + 1][n + 1][minProfit + 1];
        dp[0][0][0] = 1;
        for (int i = 1; i <= length; ++i) {
            int g = group[i - 1], p = profit[i - 1];
            for (int j = 0; j <= n; ++j) {
                for (int k = 0; k <= minProfit; ++k) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= g) {
                        dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][Math.max(0, k - p)]) % MOD;
                    }
                }
            }
        }
        int totalSchemes = 0;
        for (int j = 0; j <= n; ++j) {
            totalSchemes = (totalSchemes + dp[length][j][minProfit]) % MOD;
        }
        return totalSchemes;
    }

}

C++

#include <vector>
using namespace std;

int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
    const int MOD = 1e9 + 7;
    int length = group.size();
    vector<vector<vector<int>>> dp(length + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1, 0)));
    dp[0][0][0] = 1;
    for (int i = 1; i <= length; ++i) {
        int g = group[i - 1], p = profit[i - 1];
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= minProfit; ++k) {
                dp[i][j][k] = dp[i - 1][j][k];
                if (j >= g) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][max(0, k - p)]) % MOD;
                }
            }
        }
    }
    int totalSchemes = 0;
    for (int j = 0; j <= n; ++j) {
        totalSchemes = (totalSchemes + dp[length][j][minProfit]) % MOD;
    }
    return totalSchemes;
}

JavaScript

var profitableSchemes = function(n, minProfit, group, profit) {
    const MOD = 1e9 + 7;
    const length = group.length;
    const dp = Array.from({length: length + 1}, () => Array.from({length: n + 1}, () => Array(minProfit + 1).fill(0)));
    dp[0][0][0] = 1;
    for (let i = 1; i <= length; ++i) {
        const g = group[i - 1], p = profit[i - 1];
        for (let j = 0; j <= n; ++j) {
            for (let k = 0; k <= minProfit; ++k) {
                dp[i][j][k] = dp[i - 1][j][k];
                if (j >= g) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][Math.max(0, k - p)]) % MOD;
                }
            }
        }
    }
    let totalSchemes = 0;
    for (let j = 0; j <= n; ++j) {
        totalSchemes = (totalSchemes + dp[length][j][minProfit]) % MOD;
    }
    return totalSchemes;
};

#include <stdio.h>
#include <string.h>
#define MOD 1000000007

int profitableSchemes(int n, int minProfit, int* group, int groupSize, int* profit) {
    int dp[groupSize + 1][n + 1][minProfit + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 1; i <= groupSize; ++i) {
        int g = group[i - 1], p = profit[i - 1];
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= minProfit; ++k) {
                dp[i][j][k] = dp[i - 1][j][k];
                if (j >= g) {
                    dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - g][k > p ? k - p : 0]) % MOD;
                }
            }
        }
    }
    int totalSchemes = 0;
    for (int j = 0; j <= n; ++j) {
        totalSchemes = (totalSchemes + dp[groupSize][j][minProfit]) % MOD;
    }
    return totalSchemes;
}

using System;

public class Solution {
    public int ProfitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        const int MOD = 1000000007;
        int length = group.Length;
        var dp = new int[length + 1, n + 1, minProfit + 1];
        dp[0, 0, 0] = 1;
        for (int i = 1; i <= length; ++i) {
            int g = group[i - 1], p = profit[i - 1];
            for (int j = 0; j <= n; ++j) {
                for (int k = 0; k <= minProfit; ++k) {
                    dp[i, j, k] = dp[i - 1, j, k];
                    if (j >= g) {
                        dp[i, j, k] = (dp[i, j, k] + dp[i - 1, j - g, Math.Max(0, k - p)]) % MOD;
                    }
                }
            }
        }
        int totalSchemes = 0;
        for (int j = 0; j <= n; ++j) {
            totalSchemes = (totalSchemes + dp[length, j, minProfit]) % MOD;
        }
        return totalSchemes;
    }
}

The function `profitableSchemes` initializes a 3D dynamic programming table to track the number of schemes. It iterates over each crime, updating the possible member and profit counts. Each crime decision updates the DP table based on whether the crime is included in the solution set. The final result is obtained by summing up all combinations that meet or exceed the minimum profit using at most the total number of members.

Complexity

Time Complexity: O(L * N * P), where L is the number of crimes, N is the max number of members, and P is minProfit. Space Complexity: O(L * N * P) due to the DP table.

Try this approach in the editor

Approach 2: recursion with memoization

We design a function dfs(i, j, k), which means that we start from the i-th job, and have chosen j employees, and the current profit is k, then the number of schemes in this case is dfs(0, 0, 0).

The execution process of function dfs(i, j, k) is as follows:

If i = n, it means that all the jobs have been considered. If k geq minProfit, the number of schemes is 1, otherwise the number of schemes is 0;
If i < n, we can choose not to choose the i-th job, then the number of schemes is dfs(i + 1, j, k); if j + group[i] leq n, we can also choose the i-th job, then the number of schemes is dfs(i + 1, j + group[i], min(k + profit[i], minProfit)). Here we limit the profit upper limit to minProfit, because the profit exceeding minProfit has no effect on our answer.

Finally, return dfs(0, 0, 0).

In order to avoid repeated calculation, we can use the method of memoization. We use a three-dimensional array f to record all the results of dfs(i, j, k). When we calculate the value of dfs(i, j, k), we store it in f[i][j][k]. When we call dfs(i, j, k), if f[i][j][k] has been calculated, we return f[i][j][k] directly.

The time complexity is O(m times n times minProfit), and th e space complexity is O(m times n times minProfit). Here m and n are the number of jobs and employees, and minProfit is the minimum profit.

func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	m := len(group)
	f := make([][][]int, m)
	for i := range f {
		f[i] = make([][]int, n+1)
		for j := range f[i] {
			f[i][j] = make([]int, minProfit+1)
			for k := range f[i][j] {
				f[i][j][k] = -1
			}
		}
	}
	const mod = 1e9 + 7
	var dfs func(i, j, k int) int
	dfs = func(i, j, k int) int {
		if i >= m {
			if k >= minProfit {
				return 1
			}
			return 0
		}
		if f[i][j][k] != -1 {
			return f[i][j][k]
		}
		ans := dfs(i+1, j, k)
		if j+group[i] <= n {
			ans += dfs(i+1, j+group[i], min(k+profit[i], minProfit))
		}
		ans %= mod
		f[i][j][k] = ans
		return ans
	}
	return dfs(0, 0, 0)
}

Try this approach in the editor

Approach 3: Dynamic Programming

We define f[i][j][k] to be the number of schemes to make a profit of at least k with i jobs and j workers. Initially, we have f[0][j][0] = 1, which means that there is only one scheme to make a profit of 0 without any jobs.

For the i-th job, we can choose to work or not to work. If we do not work, then f[i][j][k] = f[i - 1][j][k]; if we work, then f[i][j][k] = f[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]. We need to enumerate j and k, and add up all the schemes.

The final answer is f[m][n][minProfit].

The time complexity is O(m times n times minProfit), and the space complexity is O(m times n times minProfit). Here m and n are the numbers of jobs and workers, and minProfit is the minimum profit to make.

func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	m := len(group)
	f := make([][][]int, m+1)
	for i := range f {
		f[i] = make([][]int, n+1)
		for j := range f[i] {
			f[i][j] = make([]int, minProfit+1)
		}
	}
	for j := 0; j <= n; j++ {
		f[0][j][0] = 1
	}
	const mod = 1e9 + 7
	for i := 1; i <= m; i++ {
		for j := 0; j <= n; j++ {
			for k := 0; k <= minProfit; k++ {
				f[i][j][k] = f[i-1][j][k]
				if j >= group[i-1] {
					f[i][j][k] += f[i-1][j-group[i-1]][max(0, k-profit[i-1])]
					f[i][j][k] %= mod
				}
			}
		}
	}
	return f[m][n][minProfit]
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: O(L * N * P), where L is the number of crimes, N is the max number of members, and P is minProfit. Space Complexity: O(L * N * P) due to the DP table.
recursion with memoization	–
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Subset Enumeration	O(2^m)	O(m)	Conceptual baseline to understand the subset search space
3D Dynamic Programming	O(m * n * minProfit)	O(m * n * minProfit)	Clear DP formulation when learning the state transitions
Space-Optimized 2D DP	O(m * n * minProfit)	O(n * minProfit)	Optimal solution for interviews and production code

Frequently asked questions

Is Profitable Schemes easy or hard?

Profitable Schemes is classified as Hard on LeetCode. The challenge comes from modeling the problem as a constrained knapsack counting problem and managing the additional profit dimension efficiently with dynamic programming.

Profitable Schemes Python/Java solution

Implement the space-optimized dynamic programming approach. Use a 2D array dp[g][p] where g is the number of members used and p is profit capped at minProfit. Update the table for each crime in reverse group order and apply modulo 1e9+7 after every addition.

How to solve Profitable Schemes in O(n)?

Pure O(n) time is not achievable because both group size and profit must be tracked. The optimal approach uses dynamic programming with complexity O(m * n * minProfit). Space can be reduced to O(n * minProfit) using state compression while maintaining the same time complexity.

What is the best approach for Profitable Schemes?

The best approach is dynamic programming using a 2D DP table that tracks group size and accumulated profit. For each crime, update states in reverse order of members and cap profit at minProfit. This runs in O(m * n * minProfit) time with O(n * minProfit) space, which fits the problem constraints.

Is Profitable Schemes asked at Google/Amazon/Meta?

Dynamic programming problems similar to Profitable Schemes appear frequently in interviews at companies like Amazon, Google, and Meta. The pattern resembles 0/1 knapsack counting problems with additional constraints, which are common in system and algorithm interviews.

What data structure is used in Profitable Schemes?

The primary data structure is a dynamic programming table (2D array) indexed by group size and profit. The input itself is stored in arrays representing the number of members required and profit generated for each crime.

What is the time complexity of Profitable Schemes?

The optimal dynamic programming solution runs in O(m * n * minProfit) time, where m is the number of crimes, n is the maximum group size, and minProfit is the profit threshold. Each crime updates all combinations of group size and profit states once.

Profitable Schemes solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: recursion with memoization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Profitable Schemes solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: recursion with memoization

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems