Python Dynamic Programming, Row Iteration O(n) space, O(mn) time.
Let m = len(grid), n = len(grid[0])\nIntuition: \n We can track the position of the balls. Initially, all balls are of positions [0..n].\n Without loss of gener
Let `m = len(grid), n = len(grid[0])`\nIntuition: \n* We can track the position of the balls. Initially, all balls are of positions `[0..n]`.\n* Without loss of generality, let ball `i` has position `pi` in `[-1..n]`\n* If the ball is not stuck, the update is straightforward: if `row[pi] == 1` then `pi = pi + 1`, otherwise `pi = pi -1`.\n* There can be only 4 case where balls get stuck:\n\t* If it is on the left of the row (`pi = 0`) and `row[pi] == -1`. \n\t* If it is on the right of the row (`pi = 0`) and `row[pi] == +1`. \n\t* If it is in the middle of the row `row[pi] = 1` and `row[pi+1] = -1`\n\t* If it is in the middle of the row `row[pi] = -1` and `row[pi-1] = 1`.\n\nGiven this, the iteration is as follow:\n* We skip the ones that already stuck.\n* We update the ball position if it not stuck.\n\nFor the space, we have to maintain the array `pos`, which will be `O(n)`\nSince we iterate each row, and in each row we go through all `pos` elements, the time is `O(mn)`\n\n```python\nclass Solution:\n    def findBall(self, grid: List[List[int]]) -> List[int]:\n        # 1. the ball can arrive at this row, or not.\n        # 2. keep track of the previous loc ball\'s id so that we know how to update it.\n        pos = list(range(len(grid[0])))\n        for row in grid:\n            for i, p in enumerate(pos):\n                if p == -1:\n                    continue\n                if p == 0 and (row[p] == -1 or p == len(row) - 1):\n                    pos[i] = -1\n                    continue\n                if p == len(row) - 1 and (row[p] == 1 or p == 0):\n                    pos[i] = -1\n                    continue\n                else:\n                    if row[p] == 1:\n                        if row[p + 1] == -1:\n                            pos[i] = -1\n                        else:\n                            pos[i] = p + 1\n                    else:\n                        if row[p-1] == 1:\n                            pos[i] = -1\n                        else:\n                            pos[i] = p - 1\n        return pos\n```
['Dynamic Programming']