2140. Solving Questions With Brainpower

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.

• For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]:
  • If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
  • If instead, question 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 <= 105
• questions[i].length == 2
• 1 <= pointsi, brainpoweri <= 105

Approach 01:

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    long long mostPoints(vector<vector<int>>& questions) {
        int numQuestions = questions.size();
        vector<long> maxPoints(numQuestions + 1);

        for (int currentIndex = numQuestions - 1; currentIndex >= 0; --currentIndex) {
            int currentPoints = questions[currentIndex][0];
            int brainpower = questions[currentIndex][1];
            int nextQuestionIndex = currentIndex + brainpower + 1;
            long nextQuestionPoints = nextQuestionIndex < numQuestions ? maxPoints[nextQuestionIndex] : 0;
            maxPoints[currentIndex] = max(currentPoints + nextQuestionPoints, maxPoints[currentIndex + 1]);
        }
        
        return maxPoints[0]; 
    }
};

from typing import List

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        numQuestions = len(questions)
        maxPoints = [0] * (numQuestions + 1)

        for currentIndex in range(numQuestions - 1, -1, -1):
            currentPoints = questions[currentIndex][0]
            brainpower = questions[currentIndex][1]
            nextQuestionIndex = currentIndex + brainpower + 1
            nextQuestionPoints = maxPoints[nextQuestionIndex] if nextQuestionIndex < numQuestions else 0
            maxPoints[currentIndex] = max(currentPoints + nextQuestionPoints, maxPoints[currentIndex + 1])
        
        return maxPoints[0]

Time Complexity:

• Iterating Through Questions:

  The algorithm iterates backward through the questions array once, processing each question in \( O(1) \) time.

• Updating Maximum Points:

  For each question, a constant amount of work is done (checking brainpower, computing max values), leading to an overall complexity of \( O(n) \).

• Total Time Complexity:

  Since all operations run in \( O(n) \), the overall time complexity is \( O(n) \).

Space Complexity:

• DP Array:

  The maxPoints array stores values for \( n+1 \) indices, leading to a space complexity of \( O(n) \).

• Auxiliary Variables:

  Integer and long variables such as currentPoints, brainpower, and nextQuestionPoints take \( O(1) \) space.

• Total Space Complexity:

  Since the dominant term is the DP array, the overall space complexity is \( O(n) \).