⌘K

Ninja's Training

MediumProblemExternal linkUpdated Sep 27, 2026

Description

A ninja is planning an n-day training schedule. Every day he does exactly one of three activities:

0: running
1: stealth training
2: fighting practice

Doing activity j on day i earns him points[i][j] merit points. He never does the same activity on two consecutive days. For example, if he runs on one day, the next day must be stealth training or fighting practice.

Given the n × 3 matrix points, return the maximum total merit points he can earn over all n days.

Days are numbered from 0, so the first day is day 0 and the last is day n − 1.

Examples

Example 1

Input: points = [[6, 9, 8], [2, 8, 1], [9, 1, 2]]

Output: 25

Explanation:

Day 0: fighting practice → 8
Day 1: stealth training → 8
Day 2: running → 9

The total is 8 + 8 + 9 = 25, and no activity repeats on consecutive days.

Grabbing day 0's largest value, 9 (stealth training), looks tempting, but then day 1 cannot use its 8, because that is also stealth training. The best schedule that starts with that 9 is 9 + 1 + 9 = 19, well short of 25.

Example 2

Input: points = [[20, 5, 5], [20, 5, 5], [20, 5, 5]]

Output: 45

Explanation: Running pays 20 every day, but it cannot be done two days in a row. The ninja runs on days 0 and 2 and does either other activity on day 1: 20 + 5 + 20 = 45.

Example 3

Input: points = [[3, 8, 5]]

Output: 8

Explanation: There is only one day, so there is no previous day to clash with. The ninja takes the largest value, 8 (stealth training).

Constraints

1 ≤ n ≤ 10^4, where n = points.length
points[i].length == 3
0 ≤ points[i][j] ≤ 1000

Editorial

Brute Force

Intuition

Why not just take the best activity each day? Because today's choice decides what is allowed tomorrow. In Example 1, taking day 0's 9 (stealth training) blocks day 1's 8, which is also stealth training, and the best the ninja can reach from there is 19. Starting with the smaller 8 (fighting practice) keeps day 1's 8 available and leads to 25. A choice that looks best today can cost more tomorrow, so the days cannot be decided one at a time.

So consider every schedule. It helps to think backwards from the last day. Suppose the ninja runs on the last day. Then the best total is the running points of that day, plus the best way to finish the day before with anything except running. That is the same question again, one day earlier.

Give the question a name. Let best(day, act) be the most points over days 0 to day, if activity act is done on day:

On day 0 there is no earlier day, so best(0, act) = points[0][act].
On any later day, yesterday must be one of the two other activities:
best(day, act) = points[day][act] + max(best(day − 1, other)) over the two other ≠ act.

The answer is the largest of best(n − 1, 0), best(n − 1, 1) and best(n − 1, 2): the last day can be any of the three.

Step-by-Step Explanation

Let's trace one of the three top-level questions for Example 1, points = [[6, 9, 8], [2, 8, 1], [9, 1, 2]]: best(2, 0), the most points if the ninja runs on day 2.

Step 1: best(2, 0) needs day 1 to be stealth training or fighting practice, so it asks best(1, 1) and best(1, 2).

Step 2: best(1, 1) needs day 0 to be running or fighting practice, so it asks best(0, 0) and best(0, 2).

Step 3: best(0, 0) is day 0, with no earlier day. It returns points[0][0] = 6.

Step 4: best(0, 2) returns points[0][2] = 8.

Step 5: best(1, 1) = points[1][1] + max(6, 8) = 8 + 8 = 16.

Step 6: best(1, 2) asks best(0, 0) and best(0, 1).

Step 7: best(0, 0) returns 6 again. It is exactly the question from Step 3, answered from scratch a second time.

Step 8: best(0, 1) returns 9.

Step 9: best(1, 2) = points[1][2] + max(6, 9) = 1 + 9 = 10.

Step 10: best(2, 0) = points[2][0] + max(16, 10) = 9 + 16 = 25.

The other two top-level questions work the same way: best(2, 1) = 12 and best(2, 2) = 18, seven calls each. The answer is max(25, 12, 18) = 25, after 21 calls in total for just 3 days.

Brute Force: Every Question Asked From Scratch — Trace best(2,0), the most points if the ninja runs on day 2. Each call asks about the two other activities on the day before, down to day 0.

Algorithm

Define best(day, act):
- If day == 0, return points[0][act].
- Otherwise, return points[day][act] plus the larger of best(day − 1, other) for the two other ≠ act.
Return the largest of best(n − 1, 0), best(n − 1, 1) and best(n − 1, 2).

Code

class Solution {
public:
    int ninjaTraining(vector<vector<int>>& points) {
        int last = points.size() - 1;
        int answer = 0;
        for (int act = 0; act < 3; act++) {
            answer = max(answer, best(last, act, points));
        }
        return answer;
    }

private:
    // Most points over days 0..day when `act` is done on `day`
    int best(int day, int act, vector<vector<int>>& points) {
        if (day == 0) return points[0][act];
        int bestBefore = 0;
        for (int other = 0; other < 3; other++) {
            if (other != act) {  // yesterday must be a different activity
                bestBefore = max(bestBefore, best(day - 1, other, points));
            }
        }
        return points[day][act] + bestBefore;
    }
};

from typing import List

class Solution:
    def ninjaTraining(self, points: List[List[int]]) -> int:
        def best(day: int, act: int) -> int:
            # Most points over days 0..day when `act` is done on `day`
            if day == 0:
                return points[0][act]
            best_before = 0
            for other in range(3):
                if other != act:  # yesterday must be a different activity
                    best_before = max(best_before, best(day - 1, other))
            return points[day][act] + best_before

        last = len(points) - 1
        return max(best(last, act) for act in range(3))

class Solution {
    public int ninjaTraining(int[][] points) {
        int last = points.length - 1;
        int answer = 0;
        for (int act = 0; act < 3; act++) {
            answer = Math.max(answer, best(last, act, points));
        }
        return answer;
    }

    // Most points over days 0..day when `act` is done on `day`
    private int best(int day, int act, int[][] points) {
        if (day == 0) return points[0][act];
        int bestBefore = 0;
        for (int other = 0; other < 3; other++) {
            if (other != act) {  // yesterday must be a different activity
                bestBefore = Math.max(bestBefore, best(day - 1, other, points));
            }
        }
        return points[day][act] + bestBefore;
    }
}

Complexity Analysis

Time Complexity: O(2^n)

Every call except those on day 0 makes two more calls, one for each allowed activity on the day before. A call on the last day therefore expands into a full binary tree with n levels, which is 2^n − 1 calls. There are three such trees, one per activity on the last day: 3 × (2^n − 1) calls. For n = 3 that is 21, as traced above. For n = 30 it is already over 3 billion, and n can be 10,000.

Space Complexity: O(n)

The calls go one level deeper per day, so at most n calls are waiting at any moment. Nothing else is stored.

Why This Approach Is Not Efficient

The brute force makes about 3 × 2^n calls. With n up to 10,000 that number has over 3,000 digits, so it will never finish.

But look at what it asks. Every call is best(day, act) for some day and one of 3 activities, so there are only 3n different questions: 9 for Example 1. The brute force made 21 calls to answer those 9, and the gap explodes as n grows. In the trace of best(2, 0) alone, best(0, 0) was solved twice, once in each branch.

The answer to best(day, act) never changes, no matter who asks. So the fix is to remember each answer the first time it is computed, and hand it back instantly after that.

Better Approach - Memoization (Top-Down DP)

Intuition

Keep the same recursion, and add a notebook, called the memo, with one slot for each (day, activity) pair: 3n slots in all.

Before computing best(day, act), look in its slot. If an answer is already there, return it immediately.
Otherwise, compute it exactly as before, write it into the slot, and then return it.

Each of the 3n questions is now computed once. Every repeat, which used to regrow a whole subtree, becomes a single look-up. This is called top-down dynamic programming: we still start from the final question and work downwards, but no question is ever solved twice.

In code, a slot starts at −1 to mean "not computed yet". That is safe because every real answer is 0 or more.

Step-by-Step Explanation

Same Example 1, points = [[6, 9, 8], [2, 8, 1], [9, 1, 2]], now asking all three endings. In the animation, grey nodes are answers read straight from the memo, and the memo is shown underneath.

Step 1: The answer is max(best(2, 0), best(2, 1), best(2, 2)). The memo starts empty.

Step 2: best(2, 0) begins exactly like the brute force, but each answer is stored the moment it is known: best(0, 0) = 6, best(0, 2) = 8, then best(1, 1) = 8 + max(6, 8) = 16.

Step 3: best(1, 2) asks for best(0, 0) again. The memo already holds 6, so it is returned instantly and nothing below it is explored. Then best(0, 1) = 9, best(1, 2) = 1 + max(6, 9) = 10, and best(2, 0) = 9 + max(16, 10) = 25.

Step 4: best(2, 1) needs best(1, 0) and best(1, 2). best(1, 0) is new, but both of its questions, best(0, 1) = 9 and best(0, 2) = 8, are in the memo. So best(1, 0) = 2 + max(9, 8) = 11.

Step 5: best(1, 2) = 10 comes from the memo, so best(2, 1) = 1 + max(11, 10) = 12.

Step 6: best(2, 2) needs best(1, 0) = 11 and best(1, 1) = 16, both from the memo, so best(2, 2) = 2 + max(11, 16) = 18.

Step 7: The answer is max(25, 12, 18) = 25.

Only 9 answers were actually computed, one per (day, activity) pair, and 6 repeats were looked up. The brute force made 21 calls. For n days it is always 3n computations.

Memoization: Each Question Answered Once — The same recursion, but every answer is written into the memo. Grey nodes are repeats read straight from the memo, so their subtrees are never explored.

Algorithm

Create memo, an n × 3 table filled with −1 (meaning "not computed").
Define best(day, act):
- If memo[day][act] is not −1, return it.
- If day == 0, the result is points[0][act].
- Otherwise the result is points[day][act] plus the larger of best(day − 1, other) for the two other ≠ act.
- Store the result in memo[day][act] and return it.
Return the largest of best(n − 1, 0), best(n − 1, 1) and best(n − 1, 2).

The recursion goes n levels deep. Python stops at 1,000 levels by default, so the Python code raises that limit first.

Code

class Solution {
public:
    int ninjaTraining(vector<vector<int>>& points) {
        int n = points.size();
        vector<vector<int>> memo(n, vector<int>(3, -1));  // -1 = not computed yet
        int answer = 0;
        for (int act = 0; act < 3; act++) {
            answer = max(answer, best(n - 1, act, points, memo));
        }
        return answer;
    }

private:
    int best(int day, int act, vector<vector<int>>& points, vector<vector<int>>& memo) {
        if (memo[day][act] != -1) return memo[day][act];  // answered before: reuse it
        int result;
        if (day == 0) {
            result = points[0][act];
        } else {
            int bestBefore = 0;
            for (int other = 0; other < 3; other++) {
                if (other != act) bestBefore = max(bestBefore, best(day - 1, other, points, memo));
            }
            result = points[day][act] + bestBefore;
        }
        memo[day][act] = result;
        return result;
    }
};

import sys
from typing import List

class Solution:
    def ninjaTraining(self, points: List[List[int]]) -> int:
        n = len(points)
        sys.setrecursionlimit(max(1000, n + 100))  # the calls go one level deep per day
        memo = [[-1] * 3 for _ in range(n)]  # -1 = not computed yet

        def best(day: int, act: int) -> int:
            if memo[day][act] != -1:
                return memo[day][act]  # answered before: reuse it
            if day == 0:
                result = points[0][act]
            else:
                best_before = 0
                for other in range(3):
                    if other != act:
                        best_before = max(best_before, best(day - 1, other))
                result = points[day][act] + best_before
            memo[day][act] = result
            return result

        return max(best(n - 1, act) for act in range(3))

import java.util.Arrays;

class Solution {
    public int ninjaTraining(int[][] points) {
        int n = points.length;
        int[][] memo = new int[n][3];
        for (int[] row : memo) Arrays.fill(row, -1);  // -1 = not computed yet
        int answer = 0;
        for (int act = 0; act < 3; act++) {
            answer = Math.max(answer, best(n - 1, act, points, memo));
        }
        return answer;
    }

    private int best(int day, int act, int[][] points, int[][] memo) {
        if (memo[day][act] != -1) return memo[day][act];  // answered before: reuse it
        int result;
        if (day == 0) {
            result = points[0][act];
        } else {
            int bestBefore = 0;
            for (int other = 0; other < 3; other++) {
                if (other != act) bestBefore = Math.max(bestBefore, best(day - 1, other, points, memo));
            }
            result = points[day][act] + bestBefore;
        }
        memo[day][act] = result;
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

There are 3n (day, activity) pairs, and each is computed once with two look-ups. Every other call is answered from the memo in constant time. That is about 6n steps in total, which is linear in n.

Space Complexity: O(n)

The memo holds 3n numbers, and the recursion can be up to n calls deep: the first call waits on day n − 2, which waits on day n − 3, and so on down to day 0.

Why This Approach Is Not Efficient

Memoization fixes the time: O(n) instead of O(2^n). The weak spot is the recursion depth. Before any answer comes back, the first call has to reach day 0, so n calls are waiting at the same time.

With n = 10,000, that is 10,000 nested calls. Python refuses to go past 1,000 by default and stops with RecursionError, which is why the Python code has to raise the limit. Java and C++ usually cope with 10,000 levels, but every level costs stack memory, and a much larger input would crash them the same way. Each call also costs more than a plain loop step.

Notice the order in which answers are actually produced: day 0 first, then day 1, then day 2. Every answer depends only on the day before. So there is no need to recurse at all: start at day 0 and fill the answers in that same order with ordinary loops.

Better Approach - Tabulation (Bottom-Up DP)

Intuition

Turn the memo into a table that is filled from the bottom up: dp[day][act] means the same thing as best(day, act), the most points over days 0 to day if activity act is done on day.

Row 0 has no earlier day, so it is just points[0].
Every later cell looks one row up at the two other activities, takes the larger, and adds today's points:
dp[day][act] = points[day][act] + max(dp[day − 1][other]) over the two other ≠ act.

Because each row needs only the row above it, filling the rows top to bottom means every value is ready before it is needed. There is no recursion and no "not computed yet" check. Filling answers from the smallest case upward like this is called bottom-up dynamic programming. The answer is the largest value in the last row.

A bonus: the finished table also tells you which schedule wins. Start at the best cell of the last row and step back to whichever allowed cell above supplied its max.

Step-by-Step Explanation

Example 1, points = [[6, 9, 8], [2, 8, 1], [9, 1, 2]]. Columns are the activities: 0 running, 1 stealth, 2 fight.

Step 1: Start with an empty 3 × 3 table.

Step 2: dp[0][0] = 6, the running points on day 0.

Step 3: dp[0][1] = 9.

Step 4: dp[0][2] = 8. Row 0 is simply points[0].

Step 5: dp[1][0] = 2 + max(dp[0][1], dp[0][2]) = 2 + max(9, 8) = 11.

Step 6: dp[1][1] = 8 + max(dp[0][0], dp[0][2]) = 8 + max(6, 8) = 16.

Step 7: dp[1][2] = 1 + max(dp[0][0], dp[0][1]) = 1 + max(6, 9) = 10.

Step 8: dp[2][0] = 9 + max(dp[1][1], dp[1][2]) = 9 + max(16, 10) = 25.

Step 9: dp[2][1] = 1 + max(dp[1][0], dp[1][2]) = 1 + max(11, 10) = 12.

Step 10: dp[2][2] = 2 + max(dp[1][0], dp[1][1]) = 2 + max(11, 16) = 18.

Step 11: The answer is the largest value in the last row: max(25, 12, 18) = 25.

Step 12: Which schedule? dp[2][0] = 25 means running on day 2, and its max came from dp[1][1] = 16, so day 1 was stealth training.

Step 13: dp[1][1] = 16 took its max from dp[0][2] = 8, so day 0 was fighting practice. The schedule is fighting, stealth, running: 8 + 8 + 9 = 25.

Tabulation: Filling the Table Day by Day — Each cell takes the larger of the two allowed cells in the row above and adds today's points. Highlighted cells are the ones the current cell reads.

Algorithm

Create an n × 3 table dp and copy points[0] into row 0.
For each day from 1 to n − 1, and each act from 0 to 2:
- dp[day][act] = points[day][act] plus the larger of dp[day − 1][other] for the two other ≠ act.
Return the largest value in row n − 1.

Code

class Solution {
public:
    int ninjaTraining(vector<vector<int>>& points) {
        int n = points.size();
        // dp[day][act] = most points over days 0..day when `act` is done on `day`
        vector<vector<int>> dp(n, vector<int>(3, 0));
        dp[0] = points[0];
        for (int day = 1; day < n; day++) {
            for (int act = 0; act < 3; act++) {
                int bestBefore = 0;
                for (int other = 0; other < 3; other++) {
                    if (other != act) bestBefore = max(bestBefore, dp[day - 1][other]);
                }
                dp[day][act] = points[day][act] + bestBefore;
            }
        }
        return max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]});
    }
};

from typing import List

class Solution:
    def ninjaTraining(self, points: List[List[int]]) -> int:
        n = len(points)
        # dp[day][act] = most points over days 0..day when `act` is done on `day`
        dp = [[0] * 3 for _ in range(n)]
        dp[0] = points[0][:]
        for day in range(1, n):
            for act in range(3):
                best_before = max(dp[day - 1][other] for other in range(3) if other != act)
                dp[day][act] = points[day][act] + best_before
        return max(dp[n - 1])

class Solution {
    public int ninjaTraining(int[][] points) {
        int n = points.length;
        // dp[day][act] = most points over days 0..day when `act` is done on `day`
        int[][] dp = new int[n][3];
        dp[0] = points[0].clone();
        for (int day = 1; day < n; day++) {
            for (int act = 0; act < 3; act++) {
                int bestBefore = 0;
                for (int other = 0; other < 3; other++) {
                    if (other != act) bestBefore = Math.max(bestBefore, dp[day - 1][other]);
                }
                dp[day][act] = points[day][act] + bestBefore;
            }
        }
        return Math.max(dp[n - 1][0], Math.max(dp[n - 1][1], dp[n - 1][2]));
    }
}

Complexity Analysis

Time Complexity: O(n)

The table has 3n cells, and each is filled with one addition and a max of two numbers. There are no repeats and no calls.

Space Complexity: O(n)

The table stores 3n numbers. There is no recursion, so no stack of waiting calls either.

Why This Approach Is Not Efficient

Tabulation is fast and safe for any n. It still stores the whole table, n rows of 3, but look at what the filling actually reads: row day uses only row day − 1. Once a row has been used to build the next one, it is never read again, so everything above the latest row is dead weight.

At n = 10,000 that is 30,000 numbers where 6 would do. So keep only yesterday's row and the row being built: six numbers, however many days there are.

Optimal Approach - Space-Optimized DP

Intuition

Keep one row, prev: the best total so far for each activity done on the most recent day. Start with prev = points[0].

For each new day, build that day's row curr from prev with the same rule as the table:

curr[act] = points[day][act] + max(prev[other]) over the two other ≠ act.

Then curr becomes the new prev, and the next day repeats the process. After the last day, the answer is the largest of the three values in prev.

Why build a separate curr instead of overwriting prev in place? curr[1] needs yesterday's prev[0]. If today's curr[0] had already been written over it, curr[1] would read today's value instead of yesterday's, and the two days would get mixed up.

Step-by-Step Explanation

Example 1 again. The two rows of the animation are prev (yesterday) and curr (today).

Step 1: prev = points[0] = [6, 9, 8].

Step 2: Day 1: curr[0] = 2 + max(9, 8) = 11.

Step 3: curr[1] = 8 + max(6, 8) = 16.

Step 4: curr[2] = 1 + max(6, 9) = 10.

Step 5: Day 1 is done, so prev = [11, 16, 10]. The old row is no longer needed.

Step 6: Day 2: curr[0] = 9 + max(16, 10) = 25.

Step 7: curr[1] = 1 + max(11, 10) = 12.

Step 8: curr[2] = 2 + max(11, 16) = 18.

Step 9: prev = [25, 12, 18].

Step 10: No days are left. The answer is max(25, 12, 18) = 25, the same as the full table, while only two rows of 3 numbers ever existed.

Space Optimization: Only Yesterday's Row — prev holds the best totals for the latest finished day and curr builds the next one. After each day, curr becomes prev.

Algorithm

Set prev = points[0].
For each day from 1 to n − 1:
- Build curr: for each act, curr[act] = points[day][act] plus the larger of prev[other] for the two other ≠ act.
- Set prev = curr.
Return the largest value in prev.

Code

class Solution {
public:
    int ninjaTraining(vector<vector<int>>& points) {
        vector<int> prev = points[0];  // best totals so far, one per activity done on the latest day
        for (int day = 1; day < (int)points.size(); day++) {
            vector<int> curr(3, 0);
            for (int act = 0; act < 3; act++) {
                int bestBefore = 0;
                for (int other = 0; other < 3; other++) {
                    if (other != act) bestBefore = max(bestBefore, prev[other]);
                }
                curr[act] = points[day][act] + bestBefore;
            }
            prev = curr;  // today's row becomes yesterday's for the next day
        }
        return max({prev[0], prev[1], prev[2]});
    }
};

from typing import List

class Solution:
    def ninjaTraining(self, points: List[List[int]]) -> int:
        prev = points[0][:]  # best totals so far, one per activity done on the latest day
        for day in range(1, len(points)):
            curr = [0, 0, 0]
            for act in range(3):
                best_before = max(prev[other] for other in range(3) if other != act)
                curr[act] = points[day][act] + best_before
            prev = curr  # today's row becomes yesterday's for the next day
        return max(prev)

class Solution {
    public int ninjaTraining(int[][] points) {
        int[] prev = points[0].clone();  // best totals so far, one per activity done on the latest day
        for (int day = 1; day < points.length; day++) {
            int[] curr = new int[3];
            for (int act = 0; act < 3; act++) {
                int bestBefore = 0;
                for (int other = 0; other < 3; other++) {
                    if (other != act) bestBefore = Math.max(bestBefore, prev[other]);
                }
                curr[act] = points[day][act] + bestBefore;
            }
            prev = curr;  // today's row becomes yesterday's for the next day
        }
        return Math.max(prev[0], Math.max(prev[1], prev[2]));
    }
}

Complexity Analysis

Time Complexity: O(n)

Each day does 3 additions and 3 two-number maxes: constant work, n times. Every day's points must be read at least once, so no correct solution can be faster than O(n).

Space Complexity: O(1)

Only prev and curr exist, 6 numbers however large n is.

Comparison:

Approach	Time	Extra space	Safe at n = 10^4?
Brute force	O(2^n)	O(n) call stack	No, far too slow
Memoization	O(n)	O(n) memo + O(n) call stack	Only with a raised recursion limit in Python
Tabulation	O(n)	O(n) table	Yes
Space-optimized	O(n)	O(1)	Yes

Going further: with k activities instead of 3, the same loop looks at k − 1 values for each cell, so it costs O(n × k²). Keeping only the best and second-best values of prev brings that down to O(n × k): every activity takes the best, except the one that produced it, which takes the second-best. The minimum-cost version of this exact problem is LeetCode's Paint House (3 colours) and Paint House II (k colours).

EASY

EASY

EASY

EASY

MEDIUM

EASY

EASY

MEDIUM

EASY

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY