Solving Questions With Brainpower — Problem & Solution
Solving Questions With Brainpower solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Solving Questions With Brainpower is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An exam has questions in a fixed order; questions[i] = [points_i, brainpower_i]. Go through them from first to last, and for each one decide to solve it or skip it:
- solving question
iearnspoints_i, but you must then skip the nextbrainpower_iquestions; - skipping question
ilets you decide freely on questioni + 1.
Return the maximum total points you can earn.
CodeKairo bound: points_i <= 10^4 (LeetCode allows 10^5) so that the answer fits in a 32-bit integer.
Example 1
Input: questions = [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Explanation: Solve question 0 (3 points, skip 1 and 2), then question 3 (2 points).
Example 2
Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: 7
Explanation: Solve questions 1 and 4.
Example 3
Input: questions = [[10,1],[3,1],[8,5]]
Output: 18
Constraints
1 <= questions.length <= 10^5questions[i].length == 21 <= points_i <= 10^41 <= brainpower_i <= 10^5
Hints for Solving Questions With Brainpower
Hint 1
Deciding forwards is awkward because solving a question blocks the next few. Think backwards.
Hint 2
Let
dp[i]be the best score from questionito the end.Hint 3
dp[i] = max(dp[i + 1], points_i + dp[i + brainpower_i + 1]), treating indices past the end as 0.
How to solve Solving Questions With Brainpower
Suffix DP: what happens after question i depends only on where you resume, so compute the best score of every suffix from right to left.
Approach
dp[n] = 0(and anything pastnis 0).- For
i = n-1down to 0:dp[i] = max(dp[i+1], points_i + dp[min(n, i + brainpower_i + 1)]). - Return
dp[0].
Why it works
At question i there are exactly two choices. Skipping leaves the suffix starting at i + 1; solving earns points_i and forces you to resume at i + brainpower_i + 1. Each continuation is an independent suffix problem whose optimum is already computed, so taking the better choice yields the optimum for suffix i.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Clamp the jump index to
n—i + brainpower_i + 1can run far past the end. - Greedy (always solve the most valuable reachable question) is wrong — example 2.
- With the original bounds (
10^5 · 10^5) the answer needs 64 bits.
Reference solution
Python
from typing import List
def mostPoints(questions: List[List[int]]) -> int:
n = len(questions)
dp = [0] * (n + 1)
for i in range(n - 1, -1, -1):
pts, bp = questions[i]
j = min(n, i + bp + 1)
dp[i] = max(dp[i + 1], pts + dp[j])
return dp[0]Java
public static int mostPoints(int[][] questions) {
int n = questions.length;
int[] dp = new int[n + 1];
for (int i = n - 1; i >= 0; i--) {
int j = (int) Math.min((long) n, (long) i + questions[i][1] + 1);
dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[j]);
}
return dp[0];
}C++
int mostPoints(vector<vector<int>>& questions) {
int n = questions.size();
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
long long jj = (long long) i + questions[i][1] + 1;
int j = jj > n ? n : (int) jj;
dp[i] = max(dp[i + 1], questions[i][0] + dp[j]);
}
return dp[0];
}JavaScript
var mostPoints = function(questions) {
var n = questions.length;
var dp = new Array(n + 1).fill(0);
for (var i = n - 1; i >= 0; i--) {
var j = Math.min(n, i + questions[i][1] + 1);
dp[i] = Math.max(dp[i + 1], questions[i][0] + dp[j]);
}
return dp[0];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming