Solving Questions With Brainpower
MedPrompt
You are given a 0-indexed 2D integer array questions where questions[i] = [pointsi, brainpoweri].
The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you pointsi points but you will be unable to solve each of the next brainpoweri questions. If you skip question i, you get to make the decision on the next question.
- For example, given
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:- If question
0is solved, you will earn3points but you will be unable to solve questions1and2. - If instead, question
0is skipped and question1is solved, you will earn4points but you will be unable to solve questions2and3.
- If question
Return the maximum points you can earn for the exam.
Example 1:
Input: questions = [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Explanation: The maximum points can be earned by solving questions 0 and 3.
- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.Example 2:
Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: 7
Explanation: The maximum points can be earned by solving questions 1 and 4.
- Skip question 0
- Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
- Unable to solve questions 2 and 3
- Solve question 4: Earn 5 points
Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.
Constraints:
1 <= questions.length <= 105questions[i].length == 21 <= pointsi, brainpoweri <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's choices into a recursive function. For each question, we explore two paths: solving it or skipping it. The function calculates the maximum points for each path by making recursive calls and returns the greater of the two. This method is intuitive but highly inefficient as it re-computes solutions for the same subproblems multiple times.
Algorithm
- Define a recursive function
solve(i)that computes the maximum points starting from questioni. - Base Case: If
iis greater than or equal to the number of questionsn, it means we are past the last question, so we return 0 points. - Recursive Step: For question
i, we have two choices:- Solve: Earn
questions[i][0]points and recursively call the function for the next available question at indexi + questions[i][1] + 1. - Skip: Earn 0 points for the current question and recursively call the function for the next question at index
i + 1.
- Solve: Earn
- The function returns the maximum value between the 'solve' and 'skip' options.
- The initial call is
solve(0).
Walkthrough
We define a recursive function, let's call it solve(index), which calculates the maximum points obtainable from questions[index] onwards.
- Base Case: If
indexis out of bounds (i.e.,index >= questions.length), it means there are no more questions to consider, so we return 0 points. - Recursive Step: For the current question at
index, we have two choices:- Solve: We gain
questions[index][0]points. We then have to skip the nextquestions[index][1]questions. The next question we can consider is atindex + questions[index][1] + 1. The total points for this choice would bequestions[index][0] + solve(index + questions[index][1] + 1). - Skip: We gain 0 points for the current question and move to the next one at
index + 1. The total points for this choice would besolve(index + 1).
- Solve: We gain
The function returns the maximum of the points from these two choices. The initial call to start the process is solve(0).
class Solution { public long mostPoints(int[][] questions) { return solve(0, questions); } private long solve(int i, int[][] questions) { // Base case: If we are past the last question, we can't earn more points. if (i >= questions.length) { return 0; } // Option 1: Solve the current question // We get points for this question and jump ahead by brainpower[i] + 1. int points = questions[i][0]; int brainpower = questions[i][1]; long pointsIfSolved = points + solve(i + brainpower + 1, questions); // Option 2: Skip the current question // We get 0 points for this question and move to the next one. long pointsIfSkipped = solve(i + 1, questions); // Return the maximum of the two options. return Math.max(pointsIfSolved, pointsIfSkipped); }}Complexity
Time
O(2^n), where n is the number of questions. For each question, the function branches into two recursive calls, leading to an exponential number of computations.
Space
O(n), where n is the number of questions. This is due to the maximum depth of the recursion stack, which can occur if we skip every question.
Trade-offs
Pros
Simple to understand and implement as it directly models the decision-making process at each step.
Cons
Extremely inefficient due to the exponential number of redundant calculations for the same subproblems.
Will result in a 'Time Limit Exceeded' (TLE) error on platforms for the given constraints.
This approach enhances the brute-force recursion by using memoization, a top-down dynamic programming technique. It avoids re-calculating results for the same subproblems by storing them in a memoization table (e.g., an array). When the function is called for a particular question index, it first checks if the result is already stored. If so, it returns the stored value; otherwise, it computes the result, stores it, and then returns it. This drastically reduces the computation time from exponential to linear.
Algorithm
- Create a memoization array
memoof sizen(number of questions), initialized with a value like -1 to indicate that a state has not been computed. - Define a recursive function
solve(i, memo). - Base Case: If
i >= n, return 0. - Memoization Check: If
memo[i]is not -1, it means the result for this index is already computed, so returnmemo[i]. - Recursive Step: If the result is not in the memo table, calculate the points for solving and skipping as in the brute-force approach.
solve_points = questions[i][0] + solve(i + questions[i][1] + 1, memo)skip_points = solve(i + 1, memo)
- Store the computed maximum of
solve_pointsandskip_pointsinmemo[i]before returning it. - The initial call is
solve(0, memo).
Walkthrough
We use the same recursive structure as the brute-force approach but add a cache (memoization array) to store the results of subproblems.
We introduce a memoization table, an array memo of size n, to store the result of solve(index). This array is initialized with a sentinel value (e.g., -1) to mark states that haven't been computed.
Inside the solve(index) function:
- We first check the base case: if
index >= n, return 0. - Then, we check our cache: if
memo[index]is not -1, we return the stored value immediately, avoiding re-computation. - If the value is not cached, we perform the same logic as the brute-force approach: calculate the maximum points from either solving or skipping the current question.
- Before returning the result, we store it in
memo[index]so it can be reused later.
import java.util.Arrays; class Solution { public long mostPoints(int[][] questions) { int n = questions.length; long[] memo = new long[n]; // Initialize memo with a value to indicate not computed Arrays.fill(memo, -1); return solve(0, questions, memo); } private long solve(int i, int[][] questions, long[] memo) { // Base case if (i >= questions.length) { return 0; } // If already computed, return stored value if (memo[i] != -1) { return memo[i]; } // Option 1: Solve the current question int points = questions[i][0]; int brainpower = questions[i][1]; long pointsIfSolved = points + solve(i + brainpower + 1, questions, memo); // Option 2: Skip the current question long pointsIfSkipped = solve(i + 1, questions, memo); // Store the result in memo and return memo[i] = Math.max(pointsIfSolved, pointsIfSkipped); return memo[i]; }}Complexity
Time
O(n). Each state `solve(i)` for `i` from 0 to `n-1` is computed only once. The work inside each function call is constant time.
Space
O(n). We use an array of size `n` for memoization, and the recursion stack can also go up to depth `n`.
Trade-offs
Pros
Drastically improves time complexity to linear.
Guarantees that each subproblem is solved only once.
Maintains the intuitive recursive structure of the problem.
Cons
The recursion depth can be large, potentially leading to a
StackOverflowErrorfor very deep recursion chains, though modern platforms often have large stack sizes.Slightly more memory usage than the bottom-up approach due to the recursion stack.
This is an iterative, or bottom-up, approach to dynamic programming. Instead of using recursion, we build the solution from the base cases up. We use a DP array, say dp, where dp[i] stores the maximum points obtainable starting from question i. By iterating backwards from the end of the questions array, we ensure that when we calculate dp[i], the values dp[i+1] (for skipping) and dp[i + brainpower + 1] (for solving) have already been computed. This approach is highly efficient and avoids the potential for stack overflow errors associated with deep recursion.
Algorithm
- Let
nbe the number of questions. - Create a DP array
dpof sizen + 1and initialize it with 0s.dp[i]will store the maximum points obtainable from questionito the end. dp[n]is the base case, representing 0 points as there are no questions left.- Iterate backwards from
i = n - 1down to0. - For each
i:- Calculate points if we solve question
i:solve_points = questions[i][0] + dp[next_index], wherenext_index = min(n, i + questions[i][1] + 1). - Calculate points if we skip question
i:skip_points = dp[i + 1]. - Update the DP table:
dp[i] = max(solve_points, skip_points).
- Calculate points if we solve question
- The final answer is
dp[0], which holds the maximum points starting from the first question.
Walkthrough
We define a DP array, dp, of size n+1, where dp[i] represents the maximum points we can earn from questions i to n-1. The extra element dp[n] serves as a convenient base case, representing 0 points since there are no questions left from index n onwards.
We iterate backwards from the second-to-last question (i = n-1) to the first question (i = 0). This reverse order is crucial because to calculate dp[i], we need the values for future states (dp[i+1] and dp[i + brainpower + 1]), which will have already been computed.
Iteration Logic: For each i from n-1 down to 0:
- Solve option: The points are
questions[i][0]plus the points from the next solvable question. The index of this next question isi + questions[i][1] + 1. We look up the pre-computed maximum points from that index, which isdp[i + questions[i][1] + 1]. We must handle the case where this index is out of bounds (>= n), in which case we add 0. A clean way is to usedp[min(n, nextIndex)]. - Skip option: The points are simply the maximum points we can get from the next question onwards, which is already stored in
dp[i+1]. - We set
dp[i]to the maximum of these two options.
The final answer is dp[0], which represents the maximum points starting from the very first question.
class Solution { public long mostPoints(int[][] questions) { int n = questions.length; // dp[i] will store the maximum points starting from question i. // We use size n+1 for a clean base case dp[n] = 0. long[] dp = new long[n + 1]; // Iterate backwards from the last question. for (int i = n - 1; i >= 0; i--) { int points = questions[i][0]; int brainpower = questions[i][1]; // Option 1: Solve question i. // The next question we can solve is at index i + brainpower + 1. int nextIndex = i + brainpower + 1; long pointsIfSolved = points; if (nextIndex < n) { pointsIfSolved += dp[nextIndex]; } // Option 2: Skip question i. // The points will be the same as if we started from question i+1. long pointsIfSkipped = dp[i + 1]; // dp[i] is the maximum of the two options. dp[i] = Math.max(pointsIfSolved, pointsIfSkipped); } // The answer is the maximum points starting from question 0. return dp[0]; }}Complexity
Time
O(n). We have a single loop that iterates `n` times, with constant time operations inside.
Space
O(n), for the DP array used to store the subproblem solutions.
Trade-offs
Pros
Very efficient in both time and space, with the same asymptotic complexity as memoization.
Avoids recursion overhead and eliminates the risk of
StackOverflowError.Often slightly faster in practice than the memoized recursive solution.
Cons
Can be slightly less intuitive to formulate compared to the direct recursive translation (top-down approach).
Requires careful determination of the iteration order.
Solutions
Solution
class Solution {private int n;private Long[] f;private int[][] questions;public long mostPoints(int[][] questions) { n = questions.length; f = new Long[n]; this.questions = questions; return dfs(0); }private long dfs(int i) { if (i >= n) { return 0; } if (f[i] != null) { return f[i]; } int p = questions[i][0], b = questions[i][1]; return f[i] = Math.max(p + dfs(i + b + 1), dfs(i + 1)); }}class Solution {public: long long mostPoints(vector<vector<int>> &questions) { int n = questions.size(); long long f[n]; memset(f, 0, sizeof(f)); function<long long(int)> dfs = [&](int i) -> long long { if (i >= n) { return 0; } if (f[i]) { return f[i]; } int p = questions[i][0], b = questions[i][1]; return f[i] = max(p + dfs(i + b + 1), dfs(i + 1)); }; return dfs(0); }};class Solution: def mostPoints(self, questions: List[List[int]]) -> int: @ cache def dfs(i: int) -> int: if i >= len(questions): return 0 p, b = questions[i] return max(p + dfs(i + b + 1), dfs(i + 1)) return dfs(0)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.