Rat Maze With Multiple Jumps

Considerations

The expected time complexity is:

O(n² × max_element)

Phase 1 performs the majority of the computation while caching results in the dp matrix.

The space complexity is:

O(n²)

due to:

• The memoization table (dp)

• The recursion call stack

Note on Auxiliary Space

Some problem statements mention an expected auxiliary space of O(1).

However, this implementation explicitly allocates:

• An O(n²) memoization matrix

• Recursive stack frames

Achieving true O(1) auxiliary space would require:

• Pure in-place backtracking

• Destructive updates to the input matrix

• Bit-level state encoding

While possible, such approaches are often avoided in production systems because they reduce readability and may introduce side effects.

Implementation

The following solution implements the two-phase approach discussed above.

class Solution {

    shortestDist(mat) {

        const n = mat.length;

        // dp array stores true/false reachability or undefined if unvisited
        const dp = Array.from({ length: n }, () =>
            Array(n).fill(undefined));

        const res = Array.from({ length: n }, () =>
            Array(n).fill(0));

        // ---- Phase 1: Check Reachability via Memoized DFS ----

        function canReach(i, j) {

            if (i >= n || j >= n || mat[i][j] === 0)
                return false;

            if (i === n - 1 && j === n - 1)
                return true;

            if (dp[i][j] !== undefined)
                return dp[i][j];

            const maxJump = mat[i][j];

            // Evaluate based on step size priority
            for (let step = 1; step <= maxJump; step++) {

                if (canReach(i, j + step))
                    return dp[i][j] = true;

                if (canReach(i + step, j))
                    return dp[i][j] = true;
            }

            return dp[i][j] = false;
        }

        // Base Edge Case Check

        if (mat[0][0] === 0 || !canReach(0, 0)) {
            return [[-1]];
        }

        // ---- Phase 2: Construct Path Greedily ----

        function build(i, j) {

            res[i][j] = 1;

            if (i === n - 1 && j === n - 1)
                return true;

            const maxJump = mat[i][j];

            for (let step = 1; step <= maxJump; step++) {

                // Right first

                if (j + step < n &&
                    canReach(i, j + step)) {

                    if (build(i, j + step))
                        return true;
                }

                // Down second

                if (i + step < n &&
                    canReach(i + step, j)) {

                    if (build(i + step, j))
                        return true;
                }
            }

            res[i][j] = 0;

            return false;
        }

        build(0, 0);

        return res;
    }
}

Complexity Analysis

Time Complexity

O(n² × max_element)

Each cell is evaluated at most once due to memoization, while exploring up to max_element possible jumps.

Space Complexity

O(n²)

Additional space is used by:

• The memoization matrix (dp)

• The result matrix (res)

• The recursive call stack

Key Takeaway

Whether you are a fresher visualizing the rat's movement through the maze or an experienced engineer evaluating complexity and design trade-offs, the core idea remains the same: eliminate unreachable paths as early as possible and ensure that traversal logic strictly follows the problem constraints.

By combining Backtracking, Memoization, and a two-phase search strategy, the solution efficiently identifies a valid path while respecting the required jump priorities and movement rules.

Summary

Rat Maze with Multiple Jumps extends the traditional maze problem by allowing variable-length jumps based on cell values. The solution uses a two-phase approach: a memoized depth-first search to determine reachability and a second traversal to reconstruct the valid path. This design improves efficiency by avoiding repeated calculations while ensuring that the path adheres to the problem's jump-priority rules.