Solving Questions With Brainpower

Medium
1488.

Solving Questions With Brainpower

Solving Questions With Brainpower is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google and Microsoft interviews.

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 i earns points_i, but you must then skip the next brainpower_i questions;
  • skipping question i lets you decide freely on question i + 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^5
  • questions[i].length == 2
  • 1 <= points_i <= 10^4
  • 1 <= brainpower_i <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} questions
 * @return {number}
 */
var mostPoints = function(questions) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 i earns points_i, but you must then skip the next brainpower_i questions;
  • skipping question i lets you decide freely on question i + 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^5
  • questions[i].length == 2
  • 1 <= points_i <= 10^4
  • 1 <= brainpower_i <= 10^5

Hints for Solving Questions With Brainpower

  1. Hint 1

    Deciding forwards is awkward because solving a question blocks the next few. Think backwards.

  2. Hint 2

    Let dp[i] be the best score from question i to the end.

  3. 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

  1. dp[n] = 0 (and anything past n is 0).
  2. For i = n-1 down to 0: dp[i] = max(dp[i+1], points_i + dp[min(n, i + brainpower_i + 1)]).
  3. 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 + 1 can 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