Solving Questions With Brainpower

You are given a 0-indexed 2D integer array questions where questions[i] = [points_i, brainpower_i]. 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_i points but you will be unable to solve each of the next brainpower_i 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.

import java.util.Arrays;

class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n];
        Arrays.fill(dp, -1);
        
        return solve(questions, 0, dp);
    }
    
    private long solve(int[][] questions, int index, long[] dp) {
        if (index >= questions.length) {
            return 0;
        }
        
        if (dp[index] != -1) {
            return dp[index];
        }
        
        // Option 1: Solve the current question
        int points = questions[index][0];
        int brainpower = questions[index][1];
        
        long solveCurrent = points + solve(questions, index + brainpower + 1, dp);
        
        // Option 2: Skip the current question
        long skipCurrent = solve(questions, index + 1, dp);
        
        dp[index] = Math.max(solveCurrent, skipCurrent);
        return dp[index];
    }
}

Naive Approach (Recursive without Memoization)

class Solution {
    public long mostPoints(int[][] questions) {
        return solve(questions, 0);
    }

    private long solve(int[][] questions, int index) {
        if (index >= questions.length) {
            return 0;
        }

        // Option 1: Solve the current question
        int points = questions[index][0];
        int brainpower = questions[index][1];

        long solveCurrent = points + solve(questions, index + brainpower + 1);

        // Option 2: Skip the current question
        long skipCurrent = solve(questions, index + 1);

        return Math.max(solveCurrent, skipCurrent);
    }
}

Optimal Approach (Dynamic Programming with Memoization)

The optimal approach uses dynamic programming with memoization to avoid redundant calculations. We create a dp array to store the maximum points that can be earned starting from each question. The solve function recursively explores the two options (solve or skip) and stores the result in the dp array. This significantly reduces the time complexity.

import java.util.Arrays;

class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n];
        Arrays.fill(dp, -1);
        
        return solve(questions, 0, dp);
    }
    
    private long solve(int[][] questions, int index, long[] dp) {
        if (index >= questions.length) {
            return 0;
        }
        
        if (dp[index] != -1) {
            return dp[index];
        }
        
        // Option 1: Solve the current question
        int points = questions[index][0];
        int brainpower = questions[index][1];
        
        long solveCurrent = points + solve(questions, index + brainpower + 1, dp);
        
        // Option 2: Skip the current question
        long skipCurrent = solve(questions, index + 1, dp);
        
        dp[index] = Math.max(solveCurrent, skipCurrent);
        return dp[index];
    }
}

Big(O) Run-time Analysis

• Naive Approach (Recursive): O(2^n), where n is the number of questions. This is because for each question, we have two choices (solve or skip), leading to an exponential number of possible paths.
• Optimal Approach (DP with Memoization): O(n), where n is the number of questions. Each question is solved at most once due to memoization.

Big(O) Space Usage Analysis

• Naive Approach (Recursive): O(n) due to the call stack in the recursion.
• Optimal Approach (DP with Memoization): O(n) for the dp array and O(n) for the call stack, resulting in O(n) space complexity.

Edge Cases and Handling

1. Empty Input:
   • If the questions array is empty, return 0.
2. Large brainpower Value:
   • If index + brainpower + 1 exceeds the array bounds, handle it gracefully by returning 0 in the recursive calls.
3. All Questions Skipped:
   • The algorithm should correctly handle the case where all questions are skipped, returning 0.
4. Questions with Zero brainpower:
   • If brainpower is 0 for any question, the next question can always be considered without skipping any further questions.

Here are the edge cases implemented in the code:

import java.util.Arrays;

class Solution {
    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n];
        Arrays.fill(dp, -1);
        
        return solve(questions, 0, dp);
    }
    
    private long solve(int[][] questions, int index, long[] dp) {
        if (index >= questions.length) {
            return 0;
        }
        
        if (dp[index] != -1) {
            return dp[index];
        }
        
        // Option 1: Solve the current question
        int points = questions[index][0];
        int brainpower = questions[index][1];
        
        long solveCurrent = points + solve(questions, index + brainpower + 1, dp);
        
        // Option 2: Skip the current question
        long skipCurrent = solve(questions, index + 1, dp);
        
        dp[index] = Math.max(solveCurrent, skipCurrent);
        return dp[index];
    }
}