Java solutions with comments | DFS with memoization | Easy-To-Understand
DFS (Accepted, 100.00% Faster)\n\n\nclass Solution {\n    public int[] findBall(int[][] grid) {\n        int[] exitColumns = new int[grid[0].length];\n        \
* DFS (Accepted, 100.00% Faster)\n\n```\nclass Solution {\n    public int[] findBall(int[][] grid) {\n        int[] exitColumns = new int[grid[0].length];\n        \n        for(int col=0; col<grid[0].length; col++) {\n            exitColumns[col] = dfs(grid, 0, col);\n        }\n        \n        return exitColumns;\n    }\n    \n    private int dfs(int[][] grid, int row, int col) {\n        \n        // ball dropped out of box or hit wall of the box\n        if(row > grid.length || col < 0 || col >= grid[0].length) {\n            return -1;\n        }\n        \n        // ball reach at the end of the box\n        if(row == grid.length) {\n            return col;\n        }\n        \n        // find "V" shaped pattern\n        if(grid[row][col] == 1) {\n            if (col < grid[0].length-1 && grid[row][col] != grid[row][col+1]) {\n                return -1;\n            }\n        } else {\n            if (col > 0 && grid[row][col-1] != grid[row][col]) {\n                return -1;\n            }\n        }\n               \n        //if grid[row][col] = 1, redirect ball to the right o/w left \n        col += grid[row][col];\n        \n        //recure till box dropped out of box or get stuck in V shap or at wall boundary\n        return dfs(grid, row+1, col); \n    }\n}\n```\n\n* With Memoization \n```\nclass Solution {\n    public int[] findBall(int[][] grid) {\n        int[] exitColumns = new int[grid[0].length];\n        \n        //Memoization in 5 steps\n        \n        // #1 : take an array to store results \n        int[][] memo = new int[grid.length+2][grid[0].length+2];\n        \n        // #2 : initialize it with -1\n        Arrays.stream(memo).forEach(arr -> Arrays.fill(arr, -1));\n        \n        for(int col=0; col<grid[0].length; col++) {\n            exitColumns[col] = dfs(grid, 0, col, memo); // #3 : pass memo to recursive function\n        }\n        \n        return exitColumns;\n    }\n    \n    private int dfs(int[][] grid, int row, int col, int[][] memo) {\n        \n        // ball dropped out of box or hit wall of the box\n        if(row > grid.length || col < 0 || col >= grid[0].length) {\n            return -1;\n        }\n        \n        // ball reach at the end of the box\n        if(row == grid.length) {\n            return col;\n        }\n        \n        // find "V" shaped pattern\n        if(grid[row][col] == 1) {\n            if (col < grid[0].length-1 && grid[row][col] != grid[row][col+1]) {\n                return -1;\n            }\n        } else {\n            if (col > 0 && grid[row][col-1] != grid[row][col]) {\n                return -1;\n            }\n        }\n              \n        //if grid[row][col] = 1, redirect ball to the right o/w left \n        col += grid[row][col];\n        \n        // #4 : return result if already stored in memo to avoid recomputaion\n        if(memo[row+1][col+1] != -1) {\n            return memo[row+1][col+1];\n        }\n        \n        //recure till box dropped out of box or get stuck in V shap or at wall boundary\n        return memo[row+1][col+1] = dfs(grid, row+1, col, memo); // #5 : store result & return it\n    }\n}\n```
['Depth-First Search', 'Recursion', 'Memoization', 'Java']