Ninja and His Friends

Hard25–30 min

Topics

Dynamic ProgrammingMatrix

Companies

Coding NinjasAmazon

Two friends start together on the top row of a grid — one at the first column, the other at the last column — and both move down one row at a time until they reach the bottom. At every row, each friend independently moves to the column directly below, or one column to either side. Find the maximum total value the two friends can collect together, where a cell they both land on at the same time only counts once. Every pair of positions' best outcome downward depends only on the (up to nine) pairs of positions reachable one row below, so working from the bottom row upward — where a pair's best outcome is simply the value(s) at that row — lets each row above be resolved using a table the sweep already computed. By the time the sweep reaches the top row, the entry for the friends' actual starting columns holds the maximum total collectible across the whole grid.

Test Case 1:

Input:grid = [[3,5,2],[6,2,7],[4,3,6]]

Output:28

Explanation:Both friends start on row 0 (columns 0 and 2) and step down one row at a time, each independently moving left, straight, or right; the best pair of paths collects 28 in total, sharing a cell's value once if both friends land on it together.

Test Case 2:

Input:grid = [[1,2],[3,4]]

Output:10

Explanation:With only 2 columns, both friends start adjacent and collect every cell across both rows: 1+2+3+4 = 10.

Test Case 3:

Input:grid = [[5,1,5]]

Output:10

Explanation:A single row: the friends simply collect their starting cells, 5 and 5, for 10.

Constraints

◆1 ≤ grid.length (rows) ≤ 15
◆1 ≤ grid[0].length (columns) ≤ 15
◆0 ≤ grid[i][j] ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Both friends start on row 0 — one at column 0, the other at the last column — and move down one row at a time. At every row, each friend independently chooses to shift one column left, stay in the same column, or shift one column right, giving up to nine possible combined moves per step, and shifting past either edge of the grid simply isn't allowed. Whenever both friends land on the same cell, its value is only collected once. From any pair of positions, the best total collectible from there downward is that row's value (for both friends) plus whichever of the reachable next-row position pairs collects the most. Once both friends reach the bottom row, there's nothing left to collect but that row itself. Trying every combination of moves at every row finds the maximum, though the same pair of positions ends up recomputed whenever different paths funnel into it.

TimeO(9^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[][] grid;
    private int n;
    private int m;

    public int ninjaAndFriends(int[][] grid) {
        this.grid = grid;
        this.n = grid.length;
        this.m = grid[0].length;
        return solve(0, 0, m - 1);
    }

    private int solve(int i, int j1, int j2) {
        if (j1 < 0 || j1 >= m || j2 < 0 || j2 >= m) return Integer.MIN_VALUE;
        if (i == n - 1) {
            return j1 == j2 ? grid[i][j1] : grid[i][j1] + grid[i][j2];
        }
        int best = Integer.MIN_VALUE;
        for (int d1 = -1; d1 <= 1; d1++) {
            for (int d2 = -1; d2 <= 1; d2++) {
                best = Math.max(best, solve(i + 1, j1 + d1, j2 + d2));
            }
        }
        int value = j1 == j2 ? grid[i][j1] : grid[i][j1] + grid[i][j2];
        return value + best;
    }
}

Optimal — Bottom-Up 2D Table Per Row

Optimal

Track, for the row currently being processed, a table indexed by "friend 1's column" and "friend 2's column" holding the best total collectible from that row downward for every possible pair of positions. The bottom row's table is just each pair's own cell values (shared once if the columns match), since nothing lies below it. For every row above that, each entry in the new table is that row's value for the pair, plus the best entry reachable in the row-below's table across the up to nine combined moves — one of left/stay/right for each friend, skipping any move that would leave the grid. Once every row has been swept through this way, the table for row 0 at (column 0, last column) — the friends' starting positions — holds the answer.

TimeO(n × m² × 9)

SpaceO(m²)