Solving Questions With Brainpower - Practice Coding Problems

Solving Questions With Brainpower - Problem

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.

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.

Input & Output

Example 1 — Basic Decision Making

$ Input: questions = [[3,2],[4,3],[4,4],[2,5]]

› Output: 7

💡 Note: Maximum points by solving questions 0 and 3: Skip question 0 (or solve it), solve question 1 for 4 points (can't solve questions 2,3), then solve question 3 for 2 points. Actually, the optimal is: solve question 1 (4 points, skip questions 2,3) + question 3 isn't available, OR solve question 0 (3 points, skip questions 1,2) + solve question 3 (2 points). Better strategy: solve questions 1 and 3 for 4+2=6, or solve question 2 for 4 points. Actually, solve question 1 (4 points, skip to question 4) + solve question 0 (3 points, skip to question 3) = 7 points total by working backwards.

Example 2 — All Skip vs Solve Dilemma

$ Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]

› Output: 7

💡 Note: Optimal strategy: solve questions at indices 1 (2 points, skip question 2,3) and 4 (5 points) for total 2+5=7 points

Example 3 — Single Question

$ Input: questions = [[21,5]]

› Output: 21

💡 Note: Only one question available, solve it for 21 points

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of questions with [points, brainpower] values

Decision

For each question: solve (gain points, skip next brainpower) or skip (move to next)

Output

Maximum points achievable with optimal strategy

Key Takeaway

🎯 Key Insight: Work backwards to determine the optimal choice at each position based on future possibilities

Asked in

G Google 15 a Amazon 12 f Meta 8 M Microsoft 6

The key insight is to work backwards from the end, deciding whether to solve or skip each question based on future optimal scores. The optimal approach uses bottom-up dynamic programming with dp[i] representing maximum points from position i onwards. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Top-Down Dynamic Programming (Memoization)	O(n)	O(n)	Use recursion with memoization to avoid recalculating same subproblems
Bottom-Up Dynamic Programming	O(n)	O(n)	Build solution from end to beginning using 1D DP array
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible combinations of solving/skipping questions recursively

Top-Down Dynamic Programming (Memoization) — Algorithm Steps

Create a memoization cache (hash map or array)
For each recursive call, check if result is already cached
If not cached, calculate result and store it before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Calculate and cache result for each index

Cache Hit

Return cached result for repeated subproblems

Optimized

Each subproblem solved exactly once

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 100000
long long memo[MAX_N];
int memo_set[MAX_N];

long long solve(int questions[][2], int n, int index) {
    if (index >= n) {
        return 0;
    }
    
    if (memo_set[index]) {
        return memo[index];
    }
    
    // Option 1: Solve current question
    long long solveScore = questions[index][0] + solve(questions, n, index + questions[index][1] + 1);
    
    // Option 2: Skip current question
    long long skipScore = solve(questions, n, index + 1);
    
    memo[index] = solveScore > skipScore ? solveScore : skipScore;
    memo_set[index] = 1;
    return memo[index];
}

long long solution(int questions[][2], int n) {
    memset(memo_set, 0, sizeof(memo_set));
    return solve(questions, n, 0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse 2D array manually
    int questions[100000][2];
    int n = 0;
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            questions[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            questions[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            n++;
        } else {
            ptr++;
        }
    }
    
    long long result = solution(questions, n);
    printf("%lld\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each of n questions is computed exactly once and cached

✓ Linear Growth

Space Complexity

O(n)

Memoization cache stores results for up to n different indices, plus O(n) recursion stack

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Top-Down Dynamic Programming (Memoization) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler