Detailed Explanation using DFS 🔥 | Java 1ms 🏃‍♂️
This problem was asked in \uD83D\uDD25 Google \uD83D\uDD25 interview.\n\n# Overview:\nFirst you have to take pen and paper. Then try to visualize what is happen
This problem was asked in \uD83D\uDD25 **Google** \uD83D\uDD25 interview.\n\n# Overview:\nFirst you have to take pen and paper. Then try to visualize what is happening. \n\nFor example 1 there is a reference drawing that looks like this:\n```\ngrid = \n[ \n  [ 1, 1, 1,-1,-1],\n  [ 1, 1, 1,-1,-1],\n  [-1,-1,-1, 1, 1],\n  [ 1, 1, 1, 1,-1],\n  [-1,-1,-1,-1,-1]\n]\n```\n\n<p align="center">\n<img src="https://assets.leetcode.com/users/images/65cf7f4e-b367-4e17-b7a9-946a0e1bf616_1667335054.032698.png" width="600"/>\n</p>\nSame way try to visualize for Example 3:\n\n```\ngrid = \n[\n  [ 1, 1, 1, 1, 1, 1],\n  [-1,-1,-1,-1,-1,-1],\n  [ 1, 1, 1, 1, 1, 1],\n  [-1,-1,-1,-1,-1,-1]\n]\n```\n\nFor this input the visualization should look like this:\n<p align="center">\n\t<img src="https://assets.leetcode.com/users/images/4e1c97e0-56d9-45c0-b6bc-fd5a3350737c_1667335768.2461417.png" width="400"/>\n</p>\n\n\nSo, the first thing you have to understand is that you will be checking for each ball one by one. When a ball is in a cell (let cell 0,0), it should look for it\'s right and left cell to take decisions.\n\nIf the current cell value is 1 then it should check it\'s right cell and vice versa. The base case is when the ball reaches the end of row. I am keeping a global variable (as memoization object) where I store the final result in **balls[]** array. To avoid unnecessary calculations, the **balls[currentBallNo]** is checked if it has value > -1.\n\nThis is an easy problem once you get the hint. Here\'s my code:   \uD83D\uDC68\u200D\uD83D\uDCBB\n\n<img src="https://assets.leetcode.com/users/images/77a8d905-0482-41c8-9bb6-75402444798c_1667334633.0513756.png" width="800"/>\n\n```\nclass Solution {\n    int[][] grid;\n    int[] balls;\n    int ROW, COL;\n    public int[] findBall(int[][] grid) {\n        this.balls = new int[grid[0].length];\n        Arrays.fill(balls, -1);\n        this.grid = grid;\n        ROW = grid.length;\n        COL = grid[0].length;\n        for(int ball=0; ball<balls.length; ball++){\n            // System.out.println("Checking for ball: "+ ball);\n            dfs(0, ball, ball);\n        }\n        return balls;\n    }\n    private void dfs(int i, int j, int ballNo){\n        if(balls[ballNo]>-1)\n            return;\n        if(i==ROW){\n            balls[ballNo] = j;\n            return;\n        }\n        if(isBound(i,j)){\n            if(grid[i][j]==1 && j<COL-1 && grid[i][j]==grid[i][j+1]){\n                dfs(i+1, j+1, ballNo);\n            }\n            else if(grid[i][j]==-1 && j>0 && grid[i][j]==grid[i][j-1])\n                dfs(i+1, j-1, ballNo);\n        }\n    }\n    \n    private boolean isBound(int i, int j){\n        return (i>=0 && i<ROW && j>=0 && j<COL);\n    }\n}\n```\n\n**Please give upvote  \uD83D\uDC4D  if this was helpful !**
['Depth-First Search', 'Java']