Watch 10 video solutions for Solving Questions With Brainpower, a medium level problem involving Array, Dynamic Programming. This walkthrough by NeetCodeIO has 11,600 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |