Java code Beats 100% of Users
Intuition\n Describe your first thoughts on how to solve this problem. \nGoal: The objective is to find the maximum moves in a grid where each move goes to a ce
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n**Goal**: The objective is to find the maximum moves in a grid where each move goes to a cell in the next column (either right, right-up, or right-down), and only if the cell you\u2019re moving to has a higher value than the current cell.\n\n**Observations**: \n- You are only allowed to move right, right-up, or right-down.\n- Keeping track of cells you\'ve already visited (using check) helps   prevent revisiting cells, which could lead to incorrect counts.\n- Since each row is checked independently, you can find the maximum steps starting from each cell in the leftmost column and return the highest value among them.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**Initial Setup**:\n- Start iterating through each row in the first column.\n- For each cell, call a recursive function (maxstep) to calculate the maximum steps starting from that cell.\n\n**Recursive Function (maxstep)**:\n- Define the base case: When you reach the last column, return a count of 1 as it\u2019s the last valid move.\n- For each valid position, check all three possible moves:\n     - Move right, right-up, or right-down only if the destination cell has a higher value and hasn\u2019t been visited yet.\n- Keep track of visited cells to avoid unnecessary recursive calls.\n\n**Maximization**:\n- After recursively finding the maximum moves for each starting cell, store the result in max if it\u2019s greater than the current value of max.\n- Return max if it reaches cols - 1, as this is the farthest possible movement.\n\n# Complexity\n- Time complexity: O(R x C) 3ms (beats 100% Users)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n        \n\n- Space complexity: O(R x C)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int maxMoves(int[][] grid) {\n        int rows = grid.length;\n        int cols = grid[0].length;\n        boolean[][] check = new boolean[rows][cols];\n        int max = 0;\n        int count = 0;\n        for (int i = 0; i < rows; i++) {\n            count = maxstep(i, 0, rows, cols, grid, check) - 1;\n            if (max < count) {\n                max = count;\n            }\n            if (max == cols - 1) {\n                return max;\n            }\n        }\n        return max;\n    }\n\n    public static int maxstep(int i, int j, int rows, int cols, int[][] grid, boolean[][] check) {\n        int max = 0;\n        int count1 = 0;\n        int count2 = 0;\n        int count3 = 0;\n        if (i == 0 && j < cols - 1) {\n            if (check[i][j + 1] == false && grid[i][j] < grid[i][j + 1]) {\n                check[i][j + 1] = true;\n                count1 = maxstep(i, j + 1, rows, cols, grid, check);\n            }\n            if (check[i + 1][j + 1] == false && grid[i][j] < grid[i + 1][j + 1]) {\n                check[i + 1][j + 1] = true;\n                count2 = maxstep(i + 1, j + 1, rows, cols, grid, check);\n            }\n            max = Math.max(count1, count2);\n        } else if (i == rows - 1 && j < cols - 1) {\n            if (check[i - 1][j + 1] == false && grid[i][j] < grid[i - 1][j + 1]) {\n                check[i - 1][j + 1] = true;\n                count1 = maxstep(i - 1, j + 1, rows, cols, grid, check);\n\n            }\n            if (check[i][j + 1] == false && grid[i][j] < grid[i][j + 1]) {\n                check[i][j + 1] = true;\n                count2 = maxstep(i, j + 1, rows, cols, grid, check);\n            }\n            max = Math.max(count1, count2);\n\n        } else if (j < cols - 1) {\n\n            if (check[i - 1][j + 1] == false && grid[i][j] < grid[i - 1][j + 1]) {\n                check[i - 1][j + 1] = true;\n                count1 = maxstep(i - 1, j + 1, rows, cols, grid, check);\n\n            }\n            if (check[i][j + 1] == false && grid[i][j] < grid[i][j + 1]) {\n                check[i][j + 1] = true;\n                count2 = maxstep(i, j + 1, rows, cols, grid, check);\n            }\n            if (check[i + 1][j + 1] == false && grid[i][j] < grid[i + 1][j + 1]) {\n                check[i + 1][j + 1] = true;\n                count3 = maxstep(i + 1, j + 1, rows, cols, grid, check);\n            }\n\n            max = Math.max(count1, Math.max(count2, count3));\n\n        }\n\n        return 1 + max;\n    }\n}\n```
['Java']