Maximum Number of Moves in a Grid — Medium Problem & Solution

You start at any cell of the first column of a grid of positive integers.

Difficulty: Medium
Topics: Arrays, Dynamic Programming, Matrix, Breadth-First Search
Asked at: Amazon, Google, Swiggy
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You start at any cell of the first column of a grid of positive integers. From (row, col) you may move to (row - 1, col + 1), (row, col + 1) or (row + 1, col + 1), but only to a cell holding a strictly greater value.

Return the maximum number of moves you can make.

Example 1

Input: grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
Output: 3
Explanation: For example 2 → 4 → 9 → 11 crosses to the last column.

Example 2

Input: grid = [[3,2,4],[2,1,9],[1,1,7]]
Output: 0
Explanation: No first-column cell has a strictly greater neighbour to its right.

Example 3

Input: grid = [[1,2],[3,4]]
Output: 1

Constraints

m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 10^5
1 <= grid[i][j] <= 10^6

How to solve Maximum Number of Moves in a Grid

Because each move goes one column right, the state is just the set of reachable rows in the current column. Sweep the columns once, carrying that set forward.

Approach

Mark every row of column 0 as reachable.
For column c, a row nr is reachable if some reachable row r in c - 1 with |nr - r| <= 1 has grid[nr][c] > grid[r][c-1].
If no row of column c is reachable, stop; the answer is c - 1.
Otherwise record c as the furthest column reached and continue.

Why it works

Paths never revisit a column, so the reachable-row set is a complete summary of everything the prefix of the walk can matter for. Once that set is empty the walk cannot continue from anywhere, and since every move advances one column, the last non-empty column index is exactly the move count.

Complexity

Time — O(m · n)
Space — O(m)

Pitfalls

The comparison is strictly greater; equal values block the move.
The answer is a count of moves, so a walk reaching column c has made c moves.
Enumerating individual paths is exponential; the reachable set collapses them.

Reference solution

Python

from typing import List

def maxMoves(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    cur = [True] * m
    best = 0
    for c in range(1, n):
        nxt = [False] * m
        any_ = False
        for r in range(m):
            if not cur[r]:
                continue
            for d in (-1, 0, 1):
                nr = r + d
                if 0 <= nr < m and grid[nr][c] > grid[r][c - 1]:
                    nxt[nr] = True
                    any_ = True
        if not any_:
            break
        cur = nxt
        best = c
    return best

JavaScript

var maxMoves = function(grid) {
    var m = grid.length, n = grid[0].length, r;
    var cur = [];
    for (r = 0; r < m; r++) cur.push(true);
    var best = 0;
    for (var c = 1; c < n; c++) {
        var nxt = [];
        for (r = 0; r < m; r++) nxt.push(false);
        var any = false;
        for (r = 0; r < m; r++) {
            if (!cur[r]) continue;
            for (var d = -1; d <= 1; d++) {
                var nr = r + d;
                if (nr < 0 || nr >= m) continue;
                if (grid[nr][c] > grid[r][c - 1]) { nxt[nr] = true; any = true; }
            }
        }
        if (!any) break;
        cur = nxt;
        best = c;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue