LeetCode 2140 - Solving Questions With Brainpower

LeetCode Problem 2140

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us an array called questions, where each element contains two integers:

• questions[i][0] represents the number of points earned if we solve question i
• questions[i][1] represents how many subsequent questions must be skipped after solving question i

We must process the questions from left to right in order. At every position, we have exactly two choices:

1. Skip the current question and move to the next one
2. Solve the current question, gain its points, and skip the next brainpoweri questions

The goal is to maximize the total number of points earned.

The important detail is that solving a question affects future choices. Once we solve question i, we cannot consider the next brainpoweri questions at all. This creates a dependency structure where each decision influences which future states are reachable.

For example, if we solve question i and its brainpower value is k, then the next available question becomes:

i + k + 1

The constraints are very important here:

• questions.length can be as large as 10^5
• Each points value and brainpower value can also be as large as 10^5

These constraints immediately tell us that exponential solutions are impossible. Since every question introduces two choices, a naive recursive solution would explore up to 2^n possibilities, which is far too slow.

The problem structure strongly suggests dynamic programming because:

• There are overlapping subproblems
• Each decision depends on future optimal decisions
• We want a maximum value over choices

Several edge cases are important:

• A question may skip beyond the end of the array
• The optimal strategy may involve skipping high point questions to allow better future combinations
• The array may contain only one question
• Every brainpower value may be very large, forcing long jumps
• The optimal answer may exceed 32-bit integer range, especially in Go

The problem guarantees valid input sizes and positive values, so we do not need to handle malformed input or negative points.

Approaches

Brute Force Approach

The brute force solution tries every possible combination of decisions.

At each question, we recursively branch into two possibilities:

• Skip the question
• Solve the question

If we solve the question, we recursively continue from the next valid index after skipping the required number of questions.

This approach is correct because it explores every legal sequence of decisions and returns the maximum total score among them.

However, the problem is that the number of states grows exponentially. Every question introduces two possible branches, so the total number of recursive paths can reach approximately 2^n.

With n = 100000, this approach is completely infeasible.

Additionally, many subproblems repeat. For example, multiple decision paths may eventually arrive at the same question index, causing the same computation to be repeated over and over.

Optimal Dynamic Programming Approach

The key observation is that the future only depends on the current index.

Suppose we define:

dp[i] = maximum points obtainable starting from question i

At question i, we again have two choices:

1. Skip the question:

dp[i + 1]

2. Solve the question:

points[i] + dp[i + brainpower[i] + 1]

The optimal answer is simply the maximum of these two choices.

This recurrence allows us to compute the solution efficiently.

Since each state depends only on future states, we can process the array from right to left. By the time we compute dp[i], all required future values are already known.

This transforms the exponential recursion into a linear-time dynamic programming solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively explores every possible decision sequence
Optimal Dynamic Programming	O(n)	O(n)	Computes each state once using bottom-up DP

Algorithm Walkthrough

1. Create a DP array of size n + 1.

We use:

dp[i] = maximum points obtainable starting from index i

The extra slot dp[n] represents the base case where there are no questions left. 2. Initialize the base case.

When we move beyond the last question, no more points can be earned:

dp[n] = 0

3. Iterate through the questions from right to left.

We process indices from:

n - 1 down to 0

We go backwards because each state depends on future states. 4. Compute the result for skipping the current question.

If we skip question i, we simply move to the next question:

skip = dp[i + 1]

5. Compute the result for solving the current question.

If we solve question i, we earn its points and jump forward:

next_index = i + brainpower + 1

The total becomes:

solve = points + dp[next_index]

If next_index exceeds n, we simply use 0. 6. Store the better choice.

The optimal result starting from i is:

dp[i] = max(skip, solve)

7. Return dp[0].

This represents the maximum points obtainable starting from the first question.

Why it works

The dynamic programming recurrence works because every valid strategy beginning at index i must start with exactly one of two actions:

• Skip the current question
• Solve the current question

These choices completely partition all possible valid strategies. Since dp[i] stores the optimal value for every future index, choosing the maximum between these two options guarantees optimality.

The backward traversal ensures that whenever we compute dp[i], all required future states have already been computed correctly.

Python Solution

from typing import List

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)

        dp = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            points, brainpower = questions[i]

            next_index = i + brainpower + 1

            solve = points
            if next_index < n:
                solve += dp[next_index]

            skip = dp[i + 1]

            dp[i] = max(solve, skip)

        return dp[0]

The implementation begins by creating a DP array where dp[i] stores the maximum points obtainable starting from question i.

The loop processes questions from right to left. This order is essential because each state depends on future states.

For every question, the code computes two possibilities:

• Solving the question
• Skipping the question

When solving a question, we calculate the next valid index after applying the brainpower skip. If this index is still within bounds, we add the previously computed DP value from that position.

The algorithm then compares the two choices and stores the better result.

Finally, dp[0] contains the optimal answer starting from the first question.

Go Solution

func mostPoints(questions [][]int) int64 {
    n := len(questions)

    dp := make([]int64, n+1)

    for i := n - 1; i >= 0; i-- {
        points := int64(questions[i][0])
        brainpower := questions[i][1]

        nextIndex := i + brainpower + 1

        solve := points
        if nextIndex < n {
            solve += dp[nextIndex]
        }

        skip := dp[i+1]

        if solve > skip {
            dp[i] = solve
        } else {
            dp[i] = skip
        }
    }

    return dp[0]
}

The Go implementation follows the exact same dynamic programming logic as the Python version.

The main difference is integer handling. Since the total score can become very large, we use int64 for the DP array and all score calculations.

Go slices are initialized using make, and we manually compute the maximum using an if statement because Go does not provide a built-in max function for integers.

Worked Examples

Example 1

Input:

questions = [[3,2],[4,3],[4,4],[2,5]]

We create:

dp = [0, 0, 0, 0, 0]

We process from right to left.

i	Question	Solve Option	Skip Option	dp[i]
3	[2,5]	2	0	2
2	[4,4]	4	2	4
1	[4,3]	4	4	4
0	[3,2]	3 + dp[3] = 5	4	5

Final DP array:

dp = [5, 4, 4, 2, 0]

Answer:

5

Optimal strategy:

• Solve question 0
• Skip questions 1 and 2
• Solve question 3

Total:

3 + 2 = 5

Example 2

Input:

questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]

Initial DP:

dp = [0, 0, 0, 0, 0, 0]

i	Question	Solve Option	Skip Option	dp[i]
4	[5,5]	5	0	5
3	[4,4]	4	5	5
2	[3,3]	3	5	5
1	[2,2]	2 + dp[4] = 7	5	7
0	[1,1]	1 + dp[2] = 6	7	7

Final DP array:

dp = [7, 7, 5, 5, 5, 0]

Answer:

7

Optimal strategy:

• Skip question 0
• Solve question 1
• Skip questions 2 and 3
• Solve question 4

Total:

2 + 5 = 7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each question is processed exactly once
Space	O(n)	The DP array stores one value per question

The algorithm performs a constant amount of work for every index in the array. Since there are n questions, the total runtime is linear.

The space complexity is also linear because we maintain a DP array of size n + 1.

Test Cases

from typing import List

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)

        dp = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            points, brainpower = questions[i]

            next_index = i + brainpower + 1

            solve = points
            if next_index < n:
                solve += dp[next_index]

            skip = dp[i + 1]

            dp[i] = max(solve, skip)

        return dp[0]

solution = Solution()

assert solution.mostPoints([[3,2],[4,3],[4,4],[2,5]]) == 5
# Provided example 1

assert solution.mostPoints([[1,1],[2,2],[3,3],[4,4],[5,5]]) == 7
# Provided example 2

assert solution.mostPoints([[10,1]]) == 10
# Single question

assert solution.mostPoints([[1,100000]]) == 1
# Brainpower skips beyond array bounds

assert solution.mostPoints([[5,1],[10,1],[15,1]]) == 20
# Best strategy skips middle question

assert solution.mostPoints([[1,1],[100,1],[1,1],[100,1]]) == 200
# Multiple high-value separated questions

assert solution.mostPoints([[100,3],[1,1],[1,1],[1,1],[50,1]]) == 150
# Large skip still allows later optimal choice

assert solution.mostPoints([[2,1],[4,1],[8,1],[16,1]]) == 20
# Alternating choices required

assert solution.mostPoints([[100000,0],[100000,0],[100000,0]]) == 300000
# No skipping at all

assert solution.mostPoints([[1,5],[2,5],[3,5],[4,5]]) == 4
# Sometimes skipping all but one is optimal

Test	Why
[[3,2],[4,3],[4,4],[2,5]]	Validates the first official example
[[1,1],[2,2],[3,3],[4,4],[5,5]]	Validates the second official example
[[10,1]]	Tests minimum array size
[[1,100000]]	Tests skipping beyond bounds
[[5,1],[10,1],[15,1]]	Ensures optimal non-greedy choices
[[1,1],[100,1],[1,1],[100,1]]	Tests combining distant high-value questions
[[100,3],[1,1],[1,1],[1,1],[50,1]]	Tests long jumps
[[2,1],[4,1],[8,1],[16,1]]	Tests alternating selections
[[100000,0],[100000,0],[100000,0]]	Tests accumulation of large values
[[1,5],[2,5],[3,5],[4,5]]	Tests cases where only one question can be chosen

Edge Cases

One important edge case occurs when solving a question skips beyond the end of the array. For example:

[[5, 100]]

If we solve the only question, the next valid index becomes far larger than the array size. A buggy implementation might attempt an out-of-bounds access. Our solution handles this safely by checking whether next_index < n before accessing the DP array.

Another important edge case is when skipping a high-value question produces a better overall result. A greedy strategy that always chooses the largest immediate points would fail on cases like:

[[10,2],[100,1],[100,1]]

Solving the first question blocks access to better future combinations. Dynamic programming correctly evaluates both possibilities and chooses the globally optimal answer.

A third important edge case involves very large total scores. Since points can reach 10^5 and there may be 10^5 questions, the total score may exceed 32-bit integer range. The Go implementation explicitly uses int64 to avoid overflow issues.

Another subtle case occurs when brainpower values are zero:

[[5,0],[10,0],[15,0]]

In this situation, solving a question does not force skipping any future questions. The implementation correctly computes:

next_index = i + 0 + 1

which simply advances to the next question normally.