Solving Questions With Brainpower

Problem Statement:-

You are given a 0-indexed 2D integer array questions where questions[i] = [points<sub>i</sub>, brainpower<sub>i</sub>].

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 points<sub>i</sub> points but you will be unable to solve each of the next brainpower<sub>i</sub> 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.

Link: https://leetcode.com/problems/solving-questions-with-brainpower/description/

Problem Explanation with examples:-

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 <= 10<sup>5</sup>

• questions[i].length == 2

• 1 <= points<sub>i</sub>, brainpower<sub>i</sub> <= 10<sup>5</sup>

Intuition:-

• There are simply two cases for each index, either we take the question or we skip it.

• If we take the question then we add the points of that question and then we skip the questions that are not allowed to be taken.

• If we skip the question then we simply move to the next question.

• DP will allow us to check each case and then we can take the maximum of all the cases.

Solution:-

• Take the length of the questions array in a variable n.

• Define a function solve(i) which returns the maximum number of points that can be obtained if we start from index I.

• If i >= n then return 0.

• Take a variable take to store the points if we take the question. Add the points of the current question and then call solve(i+questions[i][1]+1) to skip the questions that are not allowed to be taken.

• Take a variable skip to store the points if we skip the question. Call solve(i+1) to move to the next question.

• Return max(skip,take).

• Finally call solve(0) and return the answer.

Code:-

JAVA Solution

class Solution {

    long dp[];
    public long Points(int idx,int[][] questions,int n) {

        if(idx>=n) return 0;
        if(dp[idx] > 0) return dp[idx];
        int pts = questions[idx][0];
        int pwr = questions[idx][1];

        long pt1 = pts + Points(idx+pwr+1,questions,n);
        long pt2 = Points(idx+1,questions,n);

        dp[idx] = Math.max(pt1,pt2);
        return dp[idx];
    }

    public long mostPoints(int[][] questions) {
        dp = new long[questions.length];
        long maxpts = Points(0,questions,questions.length);
        return maxpts;
    }
}

Python Solution

class Solution:
    def mostPoints(self, questions: List[List[int]]) -> int:
        n = len(questions)
        @cache
        def solve(i):
            if i >= n:
                return 0

            take = questions[i][0] + solve(i+questions[i][1]+1)
            skip = solve(i+1)

            return max(skip,take)

        return solve(0)

Complexity Analysis:-

TIME:-

The time complexity is O(n) where n is the length of the questions array. This is because we are using dp and memoization to store the results of the subproblems and hence we are not repeating the calculations. We only visit each index once.

SPACE:-

The space complexity is O(n) where n is the length of the questions array. This is because we are using dp and memoization to store the results of the subproblems.

References:-

• Recursion

• DP

Connect with me:-

• Twitter

• Github

• LinkedIn