Maximum Number of Moves in a Grid

Medium
912.

Maximum Number of Moves in a Grid

Maximum Number of Moves in a Grid is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Swiggy interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxMoves = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Number of Moves in a Grid — Problem & Solution

Maximum Number of Moves in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Number of Moves in a Grid is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Swiggy interviews.

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

Hints for Maximum Number of Moves in a Grid

  1. Hint 1

    Every move advances exactly one column, so the answer is at most n - 1.

  2. Hint 2

    Track which rows of the current column are reachable rather than exploring paths one by one.

  3. Hint 3

    Sweep columns left to right; stop when no row in the next column can be reached.

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

  1. Mark every row of column 0 as reachable.
  2. 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].
  3. If no row of column c is reachable, stop; the answer is c - 1.
  4. 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

Java

public static int maxMoves(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    boolean[] cur = new boolean[m];
    Arrays.fill(cur, true);
    int best = 0;
    for (int c = 1; c < n; c++) {
        boolean[] nxt = new boolean[m];
        boolean any = false;
        for (int r = 0; r < m; r++) {
            if (!cur[r]) continue;
            for (int d = -1; d <= 1; d++) {
                int 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;
}

C++

int maxMoves(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<char> cur(m, 1);
    int best = 0;
    for (int c = 1; c < n; c++) {
        vector<char> nxt(m, 0);
        bool any = false;
        for (int r = 0; r < m; r++) {
            if (!cur[r]) continue;
            for (int d = -1; d <= 1; d++) {
                int nr = r + d;
                if (nr < 0 || nr >= m) continue;
                if (grid[nr][c] > grid[r][c - 1]) { nxt[nr] = 1; any = true; }
            }
        }
        if (!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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming