1. Problem Understanding
We are given an n × n maze where every cell contains one of three values:
1 → Move Right only
2 → Move Down only
3 → Move Right or Down
We start at (0, 0) and need to reach (n-1, n-1).
For every valid path, we need to calculate two things:
Total number of valid paths
Maximum Adventure, where Adventure is the sum of all cell values visited in the path.
The result should be:
[totalPaths, maxAdventure]
The number of paths must be calculated modulo 10^9 + 7.
2. Why Dynamic Programming?
A brute-force solution would try every possible path from the starting cell.
That becomes inefficient because the number of possible Right/Down combinations can grow very quickly.
For example, if every cell allows both directions, there can be a large number of paths.
However, notice an important property:
To reach a cell (i, j), we can only come from (i-1, j) or (i, j-1).
Therefore, instead of calculating the same information repeatedly, we can store the answer for every cell.
This is exactly what Dynamic Programming (DP) is useful for.
3. DP State
We maintain two DP arrays.
ways[i][j]
This stores:
The number of valid paths from (0,0) to (i,j).
long[][] ways = new long[n][n];
For example:
ways[i][j] = 5
means there are 5 different valid ways to reach (i,j).
maxSum[i][j]
This stores:
The maximum Adventure possible among all valid paths from (0,0) to (i,j).
int[][] maxSum = new int[n][n];
For example:
maxSum[i][j] = 15
means the highest Adventure among the paths reaching (i,j) is 15.
4. Starting Cell
We begin at (0,0).
There is exactly one way to reach the starting cell: we are already there.
Therefore:
ways[0][0] = 1;
The Adventure is simply the value of the starting cell:
maxSum[0][0] = grid[0][0];
So:
ways[0][0] = 1;
maxSum[0][0] = grid[0][0];
5. Understanding the Movement Rules
The most important part of the solution is understanding how a cell can be reached.
Suppose we want to reach:
(i, j)
There are only two possible previous cells:
(i-1, j) → from above
(i, j-1) → from left
But the previous cell must allow the required movement.
6. Coming From Above
Suppose we are moving:
(i-1, j)
↓
(i, j)
The previous cell must allow Down movement.
A cell allows Down when its value is:
2 → Down
3 → Right or Down
Therefore:
if (grid[i - 1][j] == 2 || grid[i - 1][j] == 3)
If this condition is true, all valid paths reaching (i-1,j) can continue to (i,j).
Therefore:
count = (count + ways[i - 1][j]) % MOD;
For the maximum Adventure:
maxSum[i - 1][j] + grid[i][j]
We add the current cell's value because the current cell is also part of the path.
7. Coming From the Left
Now suppose we move:
(i, j-1) → (i, j)
The previous cell must allow Right movement.
A cell allows Right when its value is:
1 → Right
3 → Right or Down
Therefore:
if (grid[i][j - 1] == 1 || grid[i][j - 1] == 3)
If valid, we add the number of paths:
count = (count + ways[i][j - 1]) % MOD;
And calculate the possible maximum Adventure:
maxSum[i][j - 1] + grid[i][j]
8. Complete Java Code
import java.util.*;
class Solution {
static final int MOD = 1000000007;
public ArrayList<Integer> findWays(int[][] grid) {
int n = grid.length;
long[][] ways = new long[n][n];
int[][] maxSum = new int[n][n];
// Starting cell
ways[0][0] = 1;
maxSum[0][0] = grid[0][0];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Starting cell is already initialized
if (i == 0 && j == 0) {
continue;
}
long count = 0;
int best = -1;
// Check cell from above
if (i > 0 &&
(grid[i - 1][j] == 2 ||
grid[i - 1][j] == 3)) {
if (ways[i - 1][j] > 0) {
count = (count + ways[i - 1][j]) % MOD;
best = Math.max(
best,
maxSum[i - 1][j] + grid[i][j]
);
}
}
// Check cell from left
if (j > 0 &&
(grid[i][j - 1] == 1 ||
grid[i][j - 1] == 3)) {
if (ways[i][j - 1] > 0) {
count = (count + ways[i][j - 1]) % MOD;
best = Math.max(
best,
maxSum[i][j - 1] + grid[i][j]
);
}
}
ways[i][j] = count;
if (count > 0) {
maxSum[i][j] = best;
}
}
}
ArrayList<Integer> result = new ArrayList<>();
result.add((int) ways[n - 1][n - 1]);
if (ways[n - 1][n - 1] == 0) {
result.add(0);
} else {
result.add(maxSum[n - 1][n - 1]);
}
return result;
}
}
9. Dry Run
Consider:
grid =
3 2
1 3
There are two possible paths.
Path 1
(0,0) → (0,1) → (1,1)
Values:
3 + 2 + 3 = 8
Path 2
(0,0) → (1,0) → (1,1)
Values:
3 + 1 + 3 = 7
Therefore:
Total paths = 2
Maximum Adventure = 8
Answer:
[2, 8]
10. DP Table Walkthrough
For the same example:
3 2
1 3
ways table
Starting:
1 ?
? ?
From (0,0) = 3, we can move both Right and Down.
So:
1 1
1 ?
Finally, (1,1) can be reached from both (0,1) and (1,0).
Therefore:
1 1
1 2
So:
ways[1][1] = 2
maxSum table
Starting:
3 ?
? ?
From the top:
3 → 2
Adventure:
3 + 2 = 5
From the left:
3 → 1
Adventure:
3 + 1 = 4
Therefore:
3 5
4 ?
At (1,1):
From above:
5 + 3 = 8
From left:
4 + 3 = 7
Take the maximum:
max(8, 7) = 8
So:
3 5
4 8
Final answer:
[2, 8]
11. Why Do We Use Math.max()?
There can be multiple paths reaching the same cell.
For example:
Path A → current cell = Adventure 15
Path B → current cell = Adventure 18
Path C → current cell = Adventure 12
We only need the maximum Adventure because the final question asks:
What is the maximum Adventure among all valid paths?
Therefore:
best = Math.max(best, candidate);
keeps the best possible value.
12. Why Do We Check ways > 0?
Consider a cell that technically has a valid incoming direction but cannot actually be reached from (0,0).
For example:
if (ways[i - 1][j] > 0)
ensures that we only use a previous cell if at least one valid path reaches it.
Otherwise, we could incorrectly calculate a path through an unreachable cell.
13. Why Is ways a long?
The number of paths can become very large.
Even though the final answer is required modulo:
10^9 + 7
we use:
long[][] ways
to safely perform the addition before applying modulo.
count = (count + ways[i - 1][j]) % MOD;
Finally, because the result is modulo 10^9 + 7, it fits into an int.
14. Why Doesn't maxSum Need Modulo?
The problem says that maxAdventure remains small enough.
Also, the maximum possible path length is limited by the grid size.
Since every valid move is either Right or Down, a path from (0,0) to (n-1,n-1) contains:
2n - 1
cells.
For n = 100, that is only:
2(100) - 1 = 199
cells.
Each cell has a maximum value of 3, so the maximum possible Adventure is:
199 × 3 = 597
Therefore an int is more than enough.
15. Why the Algorithm Is O(n²)
There are:
n × n
cells.
For every cell, we perform only a constant number of operations:
Check above
Check left
Update path count
Update maximum Adventure
Therefore:
Time Complexity = O(n²)
We also maintain two n × n arrays:
ways
maxSum
Therefore:
Space Complexity = O(n²)
This matches the expected complexity.
16. Important Observation
The key trick in this problem is to work backward conceptually.
Instead of asking:
Where can I go from this cell?
we ask:
From which cells could I have arrived at this cell?
For (i,j):
(i-1,j)
↓
(i,j-1) → (i,j)
There are only two possible previous cells.
This makes the DP transition very simple.
17. DP Formula
For the number of paths:
ways[i][j]
=
valid paths from top
+
valid paths from left
More formally:
ways[i][j] =
ways[i-1][j] if top allows Down
+ ways[i][j-1] if left allows Right
For maximum Adventure:
maxSum[i][j]
=
grid[i][j]
+
max(
maxSum[i-1][j],
maxSum[i][j-1]
)
But we only consider a previous cell if its movement direction allows reaching the current cell.
18. Common Mistakes
Mistake 1: Checking the current cell's value
When moving from (i-1,j) to (i,j), you must check:
grid[i - 1][j]
not:
grid[i][j]
Because the previous cell controls the movement.
Similarly, when moving from the left:
grid[i][j - 1]
must be checked.
Mistake 2: Forgetting the current cell in Adventure
If the previous Adventure is:
10
and the current cell contains:
3
the new Adventure is:
10 + 3 = 13
Therefore:
maxSum[previous] + grid[i][j]
is required.
Mistake 3: Forgetting the starting cell
The starting cell is also included in Adventure.
So:
maxSum[0][0] = grid[0][0];
not:
maxSum[0][0] = 0;
Mistake 4: Not handling unreachable destination
It is possible that no valid path reaches (n-1,n-1).
In that case:
ways[n - 1][n - 1] == 0
and we return:
[0, 0]
19. Final Takeaway
This problem is a classic Dynamic Programming on a Grid problem with two pieces of information being maintained simultaneously.
For every cell, we maintain:
ways → How many paths can reach here?
maxSum → What is the maximum Adventure reaching here?
The movement rules determine whether the top and left cells can contribute.
The final cell contains exactly what we need:
ways[n - 1][n - 1]
for the total number of paths, and:
maxSum[n - 1][n - 1]
for the maximum Adventure.
The overall solution runs in:
O(n²) time
O(n²) space
which is optimal for the given n ≤ 100 constraint.