C++ // DFS // Code with explanation // #1706 ✅
Solves 1706: Where Will the Ball Fall \nIf you find this post helpful, please do upvote! \u2B06\uFE0F\n\nWe have two choices for the ball: \n- Ball can move lef
Solves [1706: Where Will the Ball Fall ](https://leetcode.com/problems/where-will-the-ball-fall/)\nIf you find this post helpful, please do upvote! \u2B06\uFE0F\n\nWe have two choices for the ball: \n- Ball can move left\n- Ball can move right\n\n1) A ball can move right if the current board and the next board in the grid is like this `\\ \\`, that is if they are 1.\n2) A ball can move left if the current board and the previous board in the grid is like this `/ /`, that is if they are -1.\n\nNow using this idea run the recursion - If the ball pass through the last row then it retun the final column it is in.\n\n```\nclass Solution {\npublic:\n    \n    \n    int solve(int i, int j, vector<vector<int>>& grid, int m, int n){\n\n        // base condition: if ball passed all rows then, \n        // ball is out at jth column\n        if(i == m) return j;\n        \n        \n        /* At a time a ball can move only left or right, not both\n\t\t    so even though we have two choices, only one choise can be executed,\n\t\t\tso the recursive structure is not exponential but rather linear -> O(M)*/\n        \n        // ball can move right if current board and next board are towards right\n        if(grid[i][j] == 1 && j + 1 < n && grid[i][j + 1] == 1){\n            return solve(i + 1, j + 1, grid, m, n);\n        }\n        \n        // ball can move left if current board and previous board is towards left\n        if(grid[i][j] == -1 && j - 1 >= 0 && grid[i][j - 1] == -1){\n            return solve(i + 1, j - 1, grid, m, n);\n        }\n        \n        // if ball couldn\'t move left or right, then its trapped\n        return -1;\n    }\n    \n    vector<int> findBall(vector<vector<int>>& grid) {\n        int m = grid.size();\n        int n = grid[0].size();\n        \n        // stores the answer \n        vector<int> fall(n);\n        \n\t\t// Find the status of each ball -> O(N)\n        for(int i = 0; i < n; i++){\n            fall[i] = solve(0, i, grid, m, n);\n        }\n        \n        return fall;\n    }\n};\n```\n\n**Time Complexity: O(M N)\nSpace Complexity: O(1)**\n\n*if auxillary stack space is excluded else SC is O(M).*\n\nIf you find this post helpful, please do upvote! \u2B06\uFE0F
['Depth-First Search', 'Recursion', 'C']