Kotlin. Beats 100% (4 ms). Alternating BooleanArrays
\n\n# Code\nkotlin []\nclass Solution {\n    fun maxMoves(grid: Array<IntArray>): Int {\n        var moveY = BooleanArray(grid.size) { true }\n        var nextM
![image.png](https://assets.leetcode.com/users/images/d9595e9d-ddc0-42bb-96e9-5328c231cfd4_1730212012.858842.png)\n\n# Code\n```kotlin []\nclass Solution {\n    fun maxMoves(grid: Array<IntArray>): Int {\n        var moveY = BooleanArray(grid.size) { true }\n        var nextMoveY = BooleanArray(grid.size)\n\n        var x = 0\n        while (true) {\n            var added = false\n            for (y in 0 until moveY.size) {\n                if (moveY[y]) {\n                    val p = grid[y][x]\n                    if (y > 0 && p < grid[y - 1][x + 1]) { nextMoveY[y - 1] = true; added = true }\n                    if (p < grid[y][x + 1]) { nextMoveY[y] = true; added = true }\n                    if (y < grid.size - 1 && p < grid[y + 1][x + 1]) { nextMoveY[y + 1] = true; added = true }\n                }\n            }\n\n            if (!added) break\n\n            Arrays.fill(moveY, false)\n            moveY = nextMoveY.also { nextMoveY = moveY }\n\n            x++\n            if (x + 1 == grid[0].size) break\n        }\n        return x\n    }\n}\n```\n\n# Approach\n\nIt is probably worth pointing out right away that the DFS solution is not suitable for this problem, since with a high probability we will get to the same cells multiple times and essentially check the same solutions.\n\nInstead, we can simply move from left to right, successively increasing X by 1.\n\nAt each step with X, we must look at the list of points that were obtained at the previous step and try to find a continuation for each point on the next line. In doing so, we must immediately cut off duplicates, since duplicates will force us to check the same branches of solutions again, and this is extra work and bad runtime.\n\nWhen all the new points on the next line are found, we make a transition to this line and continue the search again.\n\n\n# Alternative approaches\n\nIt was assumed that the hash set would give a win on large matrices with a small number of available paths. But, as empirical evidence shows, it turned out to be effective only in terms of memory consumption.\n\n1. Alternating HashSets (19 ms)\n\n![image.png](https://assets.leetcode.com/users/images/56e36fac-57fb-4419-8b23-20b895c62e15_1730190417.466551.png)\n\n```kotlin []\nclass Solution {\n    fun maxMoves(grid: Array<IntArray>): Int {\n        var moveY = HashSet<Int>()\n        for (y in 0 until grid.size) {\n            moveY.add(y)\n        }\n        var nextMoveY = HashSet<Int>()\n\n        var x = 0\n        while (moveY.size > 0) {\n            for (y in moveY) {\n                val p = grid[y][x]\n                if (y > 0 && grid[y - 1][x + 1] > p) nextMoveY.add(y - 1)\n                if (grid[y][x + 1] > p) nextMoveY.add(y)\n                if (y < grid.size - 1 && grid[y + 1][x + 1] > p) nextMoveY.add(y + 1)\n            }\n\n            if (nextMoveY.size == 0) break\n\n            moveY.clear()\n            val temp = moveY\n            moveY = nextMoveY\n            nextMoveY = temp\n\n            x++\n            if (x + 1 == grid[0].size) break\n        }\n        return x\n    }\n}\n```\n\n2. Alternating BooleanArrays again\n\n![image.png](https://assets.leetcode.com/users/images/7a166634-1565-449d-860e-3227078c4baa_1730212378.8803082.png)\n\n```\nclass Solution {\n    fun maxMoves(grid: Array<IntArray>): Int {\n        var moveY = BooleanArray(grid.size) { true }\n        var nextMoveY = BooleanArray(grid.size)\n\n        var x = 0\n        do {\n            var added = false\n            loop@ for (y in 0 until moveY.size) {\n                val nextP = grid[y][x + 1]\n                for (py in y-1..y+1) {\n                    if (py >= 0 && py < grid.size && moveY[py] && grid[py][x] < nextP) {\n                        nextMoveY[y] = true\n                        added = true\n                        continue@loop\n                    }\n                }\n            }\n\n            if (!added) break\n\n            Arrays.fill(moveY, false)\n            moveY = nextMoveY.also { nextMoveY = moveY }\n\n            x++\n        } while (x < grid[0].size - 1)\n        \n        return x\n    }\n}\n```\n\n3. Making BitSets great again )\n\n![image.png](https://assets.leetcode.com/users/images/406ecef2-72f4-4c2f-aff3-ee102fa3ccad_1730211644.4363036.png)\n\n```\nclass Solution {\n    fun maxMoves(grid: Array<IntArray>): Int {\n        var moveY = BitSet(grid.size)\n        for (i in 0 until grid.size) {\n            moveY.set(i, true)\n        }\n        var nextMoveY = BitSet(grid.size)\n\n        var x = 0\n        while (x + 1 < grid[0].size) {\n            for (y in 0 until grid.size) {\n                for (py in y-1..y+1) {\n                    if (py >= 0 && py < grid.size && moveY[py] && grid[py][x] < grid[y][x + 1]) {\n                        nextMoveY.set(y, true)\n                        break\n                    }\n                }\n            }\n\n            if (nextMoveY.cardinality() == 0) break\n\n            moveY.clear()\n            moveY = nextMoveY.also { nextMoveY = moveY }\n\n            x++\n        }\n        return x\n    }\n}\n```
['Kotlin']