C++ Simple DFS
The constraints are lenient so we can simply simulate the whole process for each ball to get the answer.\n\n\nclass Solution {\n    int m,n;\n    \n    int endi
The constraints are lenient so we can simply simulate the whole process for each ball to get the answer.\n\n```\nclass Solution {\n    int m,n;\n    \n    int endingColumnOfBall(int r,int c,vector<vector<int>>& grid)\n    {\n\t\t/*\n\t\tConsidering the current cell at row r and column c\n\t\t\n\t\tThe ball gets stuck in two scenarios for each case of right and left directed board:\n\t\t\n\t\tFor right directed board (grid[r][c]==1) :-\n\t\tIt gets stuck if there is a wall on right ( c==n-1) or a left directed board on right (grid[r][c+1]==-1)\n\t\t\n\t\tSimilarly for left directed board (grid[r][c]==-1):-\n\t\tIt gets stuck if there is a wall on left ( c==0) or a right directed board on left (grid[r][c-1]==1)\n\t\t*/\n        if(grid[r][c]==1 && (c==n-1||grid[r][c+1]==-1) || grid[r][c]==-1 && (c==0||grid[r][c-1]==1))\n            return -1;\n\t\t\n\t\t/*If ball reaches last row without getting stuck then following the direction of grid[r][c]\n\t\tfor current column will give the final column\n\t\t\n\t\tWe can just add the value of grid[r][c] to c to do that\n\t\tas for right direction column will become c+1\n\t\tand for left , it will become c-1\n\t\t*/\n        if(r+1==m)\n            return c+grid[r][c];\n        \n\t\t//Otherwise we can just recursively traverse further \n\t\t//Ball goes down so r -> r+1\n\t\t//and c -> c + grid[r][c] to follow board direction\n        return endingColumnOfBall(r+1,c+grid[r][c],grid);\n    }\n    \npublic:\n    vector<int> findBall(vector<vector<int>>& grid) {\n        m = grid.size();\n        n = grid[0].size();\n        \n        vector<int> ans(n);\n        \n\t\t//Tracing the path of the ball starting from each column and finding the last column it ends up in else returning -1 if it gets stuck\n        for(int i=0;i<n;++i)\n            ans[i] = endingColumnOfBall(0,i,grid);\n        \n        return ans;\n    }\n};\n```\n\n**Time Complexity** **: O(m*n)** \nFor each of the columns we may travel only as long as the ball doesn\'t fall out of it , i.e , fall through all rows at max , so O(m) operations for each of the n columns\n\n**Space Complexity: O(n)**\nFor the space taken by the ans vector excluding recursive stack space\n\nIf we also take into consideration the recursive stack space then **Space Complexity : O(max(m,n))**
['Depth-First Search', 'C']