Ninjas Training Coding Problem

Problem statement Ninja is planing this ‘N’ days-long training schedule. Each day, he can perform any one of these three activities. (Running, Fighting Practice or Learning New Moves). Each activity has some merit points on each day. As Ninja has to improve all his skills, he can’t do the same activity in two consecutive days. Can you help Ninja find out the maximum merit points Ninja can earn? You are given a 2D array of size N*3 ‘POINTS’ with the points corresponding to each day and activity. Your task is to calculate the maximum number of merit points that Ninja can earn. For Example If the given ‘POINTS’ array is [[1,2,5], [3 ,1 ,1] ,[3,3,3] ],the answer will be 11 as 5 + 3 + 3. Detailed explanation ( Input/output format, Notes, Images ) Constraints: 1

Apr 13, 2025 - 19:23

Problem statement

Ninja is planing this ‘N’ days-long training schedule. Each day, he can perform any one of these three activities. (Running, Fighting Practice or Learning New Moves). Each activity has some merit points on each day. As Ninja has to improve all his skills, he can’t do the same activity in two consecutive days. Can you help Ninja find out the maximum merit points Ninja can earn?

You are given a 2D array of size N*3 ‘POINTS’ with the points corresponding to each day and activity. Your task is to calculate the maximum number of merit points that Ninja can earn.

For Example
If the given ‘POINTS’ array is [[1,2,5], [3 ,1 ,1] ,[3,3,3] ],the answer will be 11 as 5 + 3 + 3.
Detailed explanation ( Input/output format, Notes, Images )

Constraints:

1 <= T <= 10
1 <= N <= 100000.
1 <= values of POINTS arrays <= 100 .

Time limit: 1 sec

Test Cases

Sample Input 1:

2
3
1 2 5
3 1 1
3 3 3
3
10 40 70
20 50 80
30 60 90

Sample Output 1:

11
210

Explanation of sample input 1:

For the first test case,
One of the answers can be:
On the first day, Ninja will learn new moves and earn 5 merit points.
On the second day, Ninja will do running and earn 3 merit points.
On the third day, Ninja will do fighting and earn 3 merit points.
The total merit point is 11 which is the maximum.
Hence, the answer is 11.

For the second test case:
One of the answers can be:
On the first day, Ninja will learn new moves and earn 70 merit points.
On the second day, Ninja will do fighting and earn 50 merit points.
On the third day, Ninja will learn new moves and earn 90 merit points.
The total merit point is 210 which is the maximum.
Hence, the answer is 210.

Sample Input 2:

2
3
18 11 19
4 13 7
1 8 13
2
10 50 1
5 100 11

Sample Output 2:

45
110

Approach

Suppose if we consider the example :

|10 50 1
|5 100 11

and try to solve the problem greedily. We would take 50 points from the first row and 11 points from the second row. Why 11? It is clearly stated that we cannot do the same activity in two consecutive days; hence, a 100-point activity cannot be repeated.
But this will not increase our points.

Now, the next option we have is to try all the possibilities. Thus, recursion is the way to go.
We can represent the problem as a function that will accept two parameters.

Index
Previously done Activity.

Let us consider the following :

-> 0 means we have performed the 0th activity running
-> 1 means we have performed a fighting activity
-> 2 means we have performed the learning activity
-> 3 means we haven't done any activity till now.

We can start from the very last index, and at that time,e we haven't done any activity yet. So we can try all three activity possibilities and go up to the top.

Once we reach the base case, ie, index = 0, we can go through the task and only consider the task which is not been done previously. Track the maximum every time.

function(index, task) {
  if index = 0:
     go through the task
     track max
  return max;

  for all other index cases
     go through the task
     track the max by recursively going up through all possibilities
  return max at the end
}

There will be overlapping subproblems, and we can do memorization with a 2D dp array, dp[index][task], which will say the points we have collected up to index where the done task is task.

Time Complexity :

Recursion

Exponential Time complexity and O(N) Space Complexity
O(N * 4 * 3) Time complexity and O(N * 4) + O(N) Space complexity for recursion + memorization.
O(N * 4 * 3) Time Complexity and O(N * 4) Space complexity for Tabulation method.
O(N * 4 * 3) Time Complexity and O(4) Space complexity for Space optimized tabulation version.

Code

Recursion

import java.util.*;
public class Solution {
    public static int ninjaTraining(int n, int points[][]) {
        if (points == null || n == 0) {
            return 0;
        }
        // 0 means we have performed 0th activity running
        // 1 means we have performed fighting activity
        // 2 means we have performed learning activity
        // 3 means we haven't done any activity till now.
        return findMaxPoints(points, n - 1, 3);
    }

    private static int findMaxPoints(int [][] points, int index, int previousActivity) {
        if (index == 0) {
            int maxPoints = 0;
            int currentPoint = 0;
            for (int task = 0; task < 3; task++) {
                if (task != previousActivity) {
                    maxPoints = Math.max(maxPoints, points[0][task]);
                }
            }
            return maxPoints;
        }
        int maxPoints = 0;
        for (int task = 0; task < 3; task++) {
            if (task != previousActivity) {
                int pointsEarned = points[index][task] + findMaxPoints(points, index - 1, task);
                maxPoints = Math.max(maxPoints, pointsEarned);
            }
        }
        return maxPoints;
    }

}

Memoization

import java.util.*;
public class Solution {
    public static int ninjaTraining(int n, int points[][]) {
        if (points == null || n == 0) {
            return 0;
        }
        // 0 means we have performed 0th activity running
        // 1 means we have performed fighting activity
        // 2 means we have performed learning activity
        // 3 means we haven't done any activity till now.
        int [][] dp = new int [n][4];
        for (int [] d : dp) {
            Arrays.fill(d, -1);
        }
        return findMaxPoints(points, n - 1, 3, dp);
    }

    private static int findMaxPoints(int [][] points, int index, int previousActivity, int [][] dp) {
        if (index == 0) {
            int maxPoints = 0;
            int currentPoint = 0;
            for (int task = 0; task < 3; task++) {
                if (task != previousActivity) {
                    maxPoints = Math.max(maxPoints, points[0][task]);
                }
            }
            return maxPoints;
        }
        if (dp[index][previousActivity] != -1) {
            return dp[index][previousActivity];
        }
        int maxPoints = 0;
        for (int task = 0; task < 3; task++) {
            if (task != previousActivity) {
                int pointsEarned = points[index][task] + findMaxPoints(points, index - 1, task, dp);
                maxPoints = Math.max(maxPoints, pointsEarned);
            }
        }
        return dp[index][previousActivity] = maxPoints;
    }

}

Tabulation

import java.util.*;
public class Solution {
    public static int ninjaTraining(int n, int points[][]) {
        if (points == null || n == 0) {
            return 0;
        }
        // 0 means we have performed 0th activity running
        // 1 means we have performed fighting activity
        // 2 means we have performed learning activity
        // 3 means we haven't done any activity till now.
        int [][] dp = new int [n][4];
        for (int [] d : dp) {
            Arrays.fill(d, -1);
        }
        dp[0][0] = Math.max(points[0][1], points[0][2]);
        dp[0][1] = Math.max(points[0][0], points[0][2]);
        dp[0][2] = Math.max(points[0][0], points[0][1]);
        dp[0][3] = Math.max(points[0][0], Math.max(points[0][1], points[0][2]));
        for (int index = 1; index < n; index++) {
            for (int last = 0; last < 4; last++) {
                int maximumPoint = 0;
                for (int task = 0; task < 3; task++) {
                    if (last != task) {
                        int pointsEarned = points[index][task] + dp[index - 1][task];
                        maximumPoint = Math.max(pointsEarned, maximumPoint);
                    }

                }
                dp[index][last] = maximumPoint;
            }
        }
        return dp[n - 1][3];
    }
}

Space Optimization

The main idea behind optimization is that we just need the previous row's details to compute the current row. Thus, storing n * 4-sized dp array is not required; rather, just a 4-sized dp array is sufficient, which will store the previous row's result.

import java.util.*;
public class Solution {
    public static int ninjaTraining(int n, int points[][]) {
        if (points == null || n == 0) {
            return 0;
        }
        // 0 means we have performed 0th activity running
        // 1 means we have performed fighting activity
        // 2 means we have performed learning activity
        // 3 means we haven't done any activity till now.
        int [][] dp = new int [n][4];
        for (int [] d : dp) {
            Arrays.fill(d, -1);
        }
        int [] previous = new int [4];
        int [] current = new int [4];
        previous[0] = Math.max(points[0][1], points[0][2]);
        previous[1] = Math.max(points[0][0], points[0][2]);
        previous[2] = Math.max(points[0][0], points[0][1]);
        previous[3] = Math.max(points[0][0], Math.max(points[0][1], points[0][2]));
        for (int index = 1; index < n; index++) {
            for (int last = 0; last < 4; last++) {
                int maximumPoint = 0;
                for (int task = 0; task < 3; task++) {
                    if (last != task) {
                        int pointsEarned = points[index][task] + previous[task];
                        maximumPoint = Math.max(pointsEarned, maximumPoint);
                    }

                }
                current[last] = maximumPoint;
            }
            int [] temp = previous;
            previous = current;
            current = temp;
        }
        return previous[3];
    }
}