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.
questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.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 <= 105Problem Overview: You are given an array of questions where each element contains [points, brainpower]. Solving a question gives points but forces you to skip the next brainpower questions. The goal is to maximize total points by choosing which questions to solve or skip.
Approach 1: Recursion with Memoization (O(n) time, O(n) space)
This approach models the problem as a decision tree. At index i, you either solve the current question or skip it. Solving adds points[i] and jumps to i + brainpower[i] + 1, while skipping simply moves to i + 1. Many states repeat, so store computed results in a memo table keyed by index. Each index is evaluated once, reducing exponential recursion to linear time.
The recursive function returns the maximum points achievable starting from index i. Use memoization to avoid recomputing the same state. This technique directly expresses the decision logic and works well when you want a clear top‑down dynamic programming structure. It combines recursion with caching to efficiently explore optimal choices. The solution relies on concepts from dynamic programming and recursion.
Approach 2: Dynamic Programming (Bottom‑Up) (O(n) time, O(n) space)
The bottom‑up DP approach removes recursion by processing questions from right to left. Create a DP array where dp[i] represents the maximum points obtainable starting from question i. For each position, compute two choices: skip the question (dp[i + 1]) or solve it (points[i] + dp[i + brainpower[i] + 1] if the index exists).
Iterating backward ensures that future states are already computed. The transition becomes a simple maximum between solving and skipping. This method is cache‑friendly and avoids recursion overhead. Since each question is processed once, the total runtime is linear. The problem structure—making optimal choices while skipping ranges—fits classic array dynamic programming patterns.
Recommended for interviews: Interviewers typically expect the bottom‑up dynamic programming solution. It demonstrates that you recognize the overlapping subproblem structure and can translate recursive decisions into iterative DP transitions. Starting with the recursive memoization version often helps explain your reasoning, but converting it into the O(n) bottom‑up DP shows stronger problem‑solving maturity.
This approach leverages dynamic programming to solve the problem. You create a DP array where each element dp[i] represents the maximum points that can be earned starting from question i to the last question. You decide whether to solve or skip a question based on the potential points you can earn. The solution is filled backward, starting from the last question.
The code initializes a dp array with zeros of size n+1 where n is the number of questions. It iterates over the questions in reverse order, calculating the maximum possible points by considering either solving or skipping the current question. Finally, it returns the result stored in dp[0] which represents the maximum points from the first question.
Time Complexity: O(n)
Space Complexity: O(n)
This approach uses recursion with memoization to avoid recomputing results for overlapping subproblems. It recursively decides the maximum points by considering both solving and skipping options for each question, and stores results in a memoization array for reuse. This provides an efficient way to solve the problem since it avoids redundant calculations.
The Python solution utilizes a recursive function dfs which includes a memoization process. The result of each recursion is cached in the memo dictionary, and recursive calls are made to either solve or skip the current question, while deciding the optimal solution based on maximum points achievable. Finally, the function returns the highest points computed from position zero.
Time Complexity: O(n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n) |
| Recursion with Memoization Approach | Time Complexity: O(n) |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursion with Memoization | O(n) | O(n) | When reasoning about the decision tree first and expressing the problem in a top‑down DP style |
| Bottom‑Up Dynamic Programming | O(n) | O(n) | Preferred for production or interviews due to no recursion overhead and straightforward iteration |
Solving Questions with Brainpower - Leetcode 2140 - Python • NeetCodeIO • 11,600 views views
Watch 9 more video solutions →Practice Solving Questions With Brainpower with our built-in code editor and test cases.
Practice on FleetCode