Solving Questions With Brainpower

Medium

Asked by:

40 views

Topics:

Dynamic Programming

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.

Constraints:

1 <= questions.length <= 10⁵
questions[i].length == 2
1 <= points_i, brainpower_i <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value for `brainpower` and `points`? Are they always non-negative integers?
Can the input array `questions` be empty or null?
If there are multiple ways to maximize points, is any valid solution acceptable?
If skipping a question leads to going out of bounds of the `questions` array, should I consider it as the end of the path or is it an invalid move?
Is the number of questions guaranteed to be within a certain range, and what is that range?

Brute Force Solution

Approach

The brute force strategy tries every possible path through the available questions. We explore each question, deciding whether to solve it or skip it, and see what happens.

Here's how the algorithm would work step-by-step:

Start with the first question.
Consider two options: either solve this question, or skip it and move to the next.
If you solve the question, you have to skip the next few questions based on the brainpower you get, then move on to the first available question after the skipped ones.
If you skip the question, you simply move to the very next question.
Repeat the above process for each question until you reach the end of the list of questions.
Keep track of the total points earned for each possible combination of solved and skipped questions.
After exploring all possible combinations, compare the total points from each combination and choose the one with the maximum points.

Code Implementation

def max_points_brute_force(questions):
    def solve_recursive(current_index, total_points):
        # Reached end, return accumulated points
        if current_index >= len(questions):
            return total_points

        # Option 1: Skip the current question
        skip_points = solve_recursive(current_index + 1, total_points)

        # Option 2: Solve the current question
        points_from_question, brainpower_from_question = questions[current_index]

        # Calculate index after skipping brainpower
        next_index = current_index + brainpower_from_question + 1

        solve_points = solve_recursive(next_index, total_points + points_from_question)

        # Compare both options and return the maximum
        return max(skip_points, solve_points)

    return solve_recursive(0, 0)

Big(O) Analysis

Time Complexity

O(2^n) – The brute force solution explores all possible combinations of solving or skipping each question. For each of the n questions, we have two choices: solve or skip. This leads to 2 * 2 * ... * 2 (n times) possible combinations, or 2^n. Therefore, the time complexity is directly proportional to the number of combinations we need to evaluate. Thus the complexity scales exponentially with the number of questions.

Space Complexity

O(N) – The described brute force approach can be implemented using recursion. In the worst-case scenario, we explore every possible path of solving or skipping questions, leading to a recursion depth proportional to the number of questions, N. Each recursive call requires a stack frame to store function parameters and local variables. Therefore, the maximum recursion depth is N, resulting in O(N) space complexity due to the call stack.

Optimal Solution

Approach

The best way to solve this problem is to work backward. Instead of starting from the beginning and figuring out what to do, we start from the end and work our way back, making the best choices possible at each step. This ensures we get the maximum points.

Here's how the algorithm would work step-by-step:

Think about the last question: Do you solve it, or skip it? Choose the option that gives you the highest score, knowing that you don't have any more questions after that one.
Now, move to the second-to-last question. Again, decide whether to solve it or skip it. But this time, when you skip, remember that it might affect your ability to answer future questions.
Keep doing this, moving backwards through the questions, always choosing the best option at each step, taking into account how your choice impacts later questions.
By working backward and always picking the optimal immediate choice, you guarantee that you'll end up with the highest total score possible.

Code Implementation

def max_points(questions):
    number_of_questions = len(questions)
    maximum_points = [0] * number_of_questions

    maximum_points[number_of_questions - 1] = questions[number_of_questions - 1][0]

    for i in range(number_of_questions - 2, -1, -1):
        # Decide whether to solve this question or skip it
        solve_question = questions[i][0]
        skip_question = 0

        # Calculate points if we solve current question
        if i + questions[i][1] + 1 < number_of_questions:

            solve_question += maximum_points[i + questions[i][1] + 1]

        # Calculate points if we skip the current question
        skip_question = maximum_points[i + 1]

        #Store the maximum points possible
        maximum_points[i] = max(solve_question, skip_question)

    # Working backwards, the first element holds total max points.
    return maximum_points[0]

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates backward through the questions array once. For each question, it makes a constant-time decision: either solve it or skip it. The skip decision involves looking ahead a fixed number of questions (brainpower), which is still a constant-time operation. Therefore, the time complexity is directly proportional to the number of questions, n, resulting in O(n).

Space Complexity

O(N) – The algorithm works backward through the questions, making optimal choices at each step. To store the maximum points achievable from each question to the end, a dynamic programming table (an array) of size N is used, where N is the number of questions. This table stores intermediate results to avoid recomputation. Therefore, the auxiliary space required is proportional to the number of questions. The space complexity is O(N).

Edge Cases

Case	How to Handle
Empty questions array	Return 0 immediately as no questions can be solved and therefore no brainpower is required.
Questions array with a single question	Return the points of the single question as solving it results in that much brainpower being earned.
Questions array where all questions have 0 brainpower drain	Iterate through the questions array and simply take the maximum possible points, as no brainpower is ever lost from skipping.
Questions array where all questions have very high brainpower drain, exceeding array bounds	Use dynamic programming to choose only questions whose skip length allows for valid choices after it.
Large number of questions (close to maximum array size) with high points value	Ensure the dynamic programming table is large enough to handle it without out-of-memory errors and use long to handle potentially large point values.
Questions array with negative points or brainpower drain	If negative points are possible, the DP logic must account for potentially negative total points at any point; if negative brainpower is possible, filter for 0.
Questions array with points set to the maximum integer value	Use long to prevent possible integer overflow when adding up the points during the dynamic programming process.
Questions array where solving the first question makes all subsequent questions unreachable	DP solution must consider both choosing and skipping the first question to maximize points.

Empty questions array

How to Handle:

Return 0 immediately as no questions can be solved and therefore no brainpower is required.

Questions array with a single question

How to Handle:

Return the points of the single question as solving it results in that much brainpower being earned.

Questions array where all questions have 0 brainpower drain

How to Handle:

Iterate through the questions array and simply take the maximum possible points, as no brainpower is ever lost from skipping.

Questions array where all questions have very high brainpower drain, exceeding array bounds

How to Handle:

Use dynamic programming to choose only questions whose skip length allows for valid choices after it.

Large number of questions (close to maximum array size) with high points value

How to Handle:

Ensure the dynamic programming table is large enough to handle it without out-of-memory errors and use long to handle potentially large point values.

Questions array with negative points or brainpower drain

How to Handle:

If negative points are possible, the DP logic must account for potentially negative total points at any point; if negative brainpower is possible, filter for 0.

Questions array with points set to the maximum integer value

How to Handle:

Use long to prevent possible integer overflow when adding up the points during the dynamic programming process.

Questions array where solving the first question makes all subsequent questions unreachable

How to Handle:

DP solution must consider both choosing and skipping the first question to maximize points.