Grid max sum path with depth first search

You are fifteen minutes into a technical interview and the interviewer slides a grid of numbers across the table. "Given this grid," they say, "find the path from the top-left corner to the bottom-right corner that gives you the largest possible sum. You can only move down or to the right." This problem, also known as "Maximum Path Sum in Grid" on other platforms, tests your grasp of recursive thinking and depth-first search. It also sets the stage for dynamic programming, since DFS alone struggles with large inputs.

TL;DR

Use depth-first search to explore every path from the top-left cell to the bottom-right cell, moving only down or right. At each cell, branch into both directions and return the maximum sum of the two. The base case returns -1 for out-of-bounds positions and sum + grid[r][c] when you reach the destination. This runs in O(2^{(m+n)}) time and O(m+n) space. For grids up to 20x20 this works fine, but for larger inputs you would want dynamic programming instead.

Why This Problem Matters

Grid path problems appear regularly in interviews because they bridge the gap between brute-force recursion and optimization techniques. The DFS version teaches you to think about exhaustive search, recursive decomposition, and base case design. Once you see how the recursion tree explodes, the motivation for memoization and dynamic programming becomes obvious. This problem is a stepping stone to more advanced grid-based problems.

Understanding the Problem

You are given an m x n grid of non-negative integers. Starting from the top-left cell (0, 0), you need to reach the bottom-right cell (m-1, n-1). At each step, you can only move one cell down or one cell to the right. Your goal is to find the path that maximizes the sum of all cells visited along the way.

Here is a 3x3 example grid:

From cell (0,0), you can move either down to (1,0) or right to (0,1). This constraint limits you to exactly m + n - 2 moves for any complete path.

Finding the Maximum Sum Path

For the grid [[1,2,3],[4,5,6],[7,8,9]], the maximum sum path is 1 + 4 + 7 + 8 + 9 = 29, following the route down, down, right, right:

Other paths yield smaller sums. For instance, going right, right, down, down gives 1 + 2 + 3 + 6 + 9 = 21.

Edge Cases

1. Single cell: A 1x1 grid has only one path, so the answer is the cell's value.
2. Single row: The only path is moving right across all cells.
3. Single column: The only path is moving down through all cells.
4. All zeros: The maximum sum is 0.

Solution Approach: Depth-First Search

The idea is straightforward: explore every possible path from (0,0) to (m-1, n-1) and return the maximum sum found.

At each cell (r, c), you have two choices: move down to (r+1, c) or move right to (r, c+1). You add the current cell's value to a running sum and recurse in both directions. When you reach the bottom-right cell, you return the accumulated sum. When you go out of bounds, you return -1 to signal an invalid path.

The Recursion Tree

To see how DFS works, consider a tiny 2x2 grid [[1,2],[3,4]]. The recursion tree branches at each cell:

From dfs(0,0), we branch into dfs(1,0) (moving down) and dfs(0,1) (moving right). Each of those branches again until we either reach the destination or go out of bounds. The left branch finds the path 1 + 3 + 4 = 8, while the right branch finds 1 + 2 + 4 = 7. We take the maximum: 8.

Notice how dfs(1,1) is called twice with different accumulated sums. On a larger grid, this overlap grows rapidly. That is why DFS has exponential time complexity, and why dynamic programming is the better choice for production-scale inputs.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int maxSumDfs(int[][] grid) {
    return dfs(grid, 0, 0, 0);
  }

  private int dfs(int[][] grid, int r, int c, int sum) {
    if (r >= grid.length || c >= grid[0].length) return -1;
    else if (r == grid.length - 1 && c == grid[0].length - 1)
      return sum + grid[r][c];
    else return Math.max(
        dfs(grid, r + 1, c, sum + grid[r][c]),
        dfs(grid, r, c + 1, sum + grid[r][c]));
  }
}

Let's walk through the logic:

1. Entry point: maxSumDfs calls dfs(grid, 0, 0, 0), starting from the top-left with a sum of 0.
2. Out of bounds: If r or c exceeds the grid dimensions, return -1. Since all values are non-negative, -1 will never be chosen over a valid path.
3. Destination reached: If we are at the bottom-right cell (m-1, n-1), return sum + grid[r][c].
4. Recursive case: Add the current cell's value to sum, then recurse in both directions. Return whichever branch yields the larger total.

The helper method carries four parameters: the grid itself, the current row r, the current column c, and the running sum accumulated so far. This accumulator pattern avoids needing to recompute partial sums.

Complexity Analysis

Time Complexity: O(2^{(m+n)})

At each cell, the algorithm makes two recursive calls (down and right). The maximum depth of the recursion tree is m + n - 2 (the number of moves in any path). This creates up to 2^{(m+n-2)} leaf nodes. For a 3x3 grid that is manageable, but for a 20x20 grid you are already looking at roughly 2^{38} operations.

Space Complexity: O(m + n)

The space is determined by the maximum recursion depth. Every path from (0,0) to (m-1, n-1) takes exactly m + n - 2 steps, so the call stack never exceeds m + n - 1 frames. No additional data structures are used.

Why This Matters

The exponential blowup is the entire reason this problem exists as a stepping stone. Once you understand the waste in the recursion tree (repeated subproblems with overlapping cell visits), the leap to dynamic programming feels natural. The DP version fills a table in O(m * n) time by computing each cell's max sum exactly once.

Common Pitfalls

1. Forgetting to add the current cell's value: A common mistake is passing sum unchanged to the recursive calls instead of sum + grid[r][c].

2. Wrong base case for out-of-bounds: Returning 0 instead of -1 for invalid positions can cause the algorithm to prefer out-of-bounds paths over valid ones when grid values are small.

3. Checking only one boundary: Both r >= grid.length and c >= grid[0].length must be checked. Forgetting one leads to array index out of bounds errors.

4. Not handling single-cell grids: If the grid is 1x1, the function should return grid[0][0] directly. The base case r == grid.length - 1 && c == grid[0].length - 1 handles this correctly.

Interview Tips

When presenting this solution in an interview:

1. Start by clarifying constraints: Ask about grid dimensions, value ranges, and whether diagonal movement is allowed. The small constraint (up to 20x20) signals that an exponential approach is acceptable.

2. Draw the grid and trace a path: Sketch a small example and trace two different paths to show how the sum changes. This demonstrates your understanding before you write any code.

3. Mention the DP alternative proactively: After explaining the DFS solution, note that it has exponential complexity and that you would use dynamic programming for larger inputs. This shows depth of knowledge.

4. Discuss the recursion tree: If asked about optimizations, draw the recursion tree for a 2x2 grid and point out the repeated calls. This naturally leads to memoization as an intermediate step before full DP.

Key Takeaways

• Depth-first search explores all possible paths by branching down and right at each cell, returning the maximum sum found across all branches.
• The base cases are critical: return -1 for out-of-bounds positions and sum + grid[r][c] at the destination. Since grid values are non-negative, -1 guarantees invalid paths are never selected.
• Time complexity is O(2^{(m+n)}), which is only practical for small grids (up to roughly 20x20). For larger inputs, dynamic programming reduces this to O(m * n).
• The accumulator parameter sum tracks the running total as you recurse, avoiding redundant addition when returning from recursive calls.
• This problem is a natural bridge from brute-force recursion to dynamic programming. Understanding why the recursion tree has exponential nodes is the key insight that motivates DP.

Solutions in Other Languages

Python

class Solution:
    def max_sum_dfs(self, grid):
        return self.dfs(grid, 0, 0, 0)

    def dfs(self, grid, r, c, branch_sum):
        if r >= len(grid) or c >= len(grid[0]):
            return -1
        elif r == len(grid) - 1 and c == len(grid[0]) - 1:
            return branch_sum + grid[r][c]
        else:
            return max(
                self.dfs(grid, r + 1, c, branch_sum + grid[r][c]),
                self.dfs(grid, r, c + 1, branch_sum + grid[r][c])
            )

JavaScript

class Solution {
  maxSumDfs(grid) {
    return this.dfs(grid, 0, 0, 0);
  }

  dfs(grid, r, c, sum) {
    if (r >= grid.length || c >= grid[0].length) return -1;
    else if (r === grid.length - 1 && c === grid[0].length - 1)
      return sum + grid[r][c];
    else return Math.max(
        this.dfs(grid, r + 1, c, sum + grid[r][c]),
        this.dfs(grid, r, c + 1, sum + grid[r][c]));
  }
}

TypeScript

class Solution {
  maxSumDfs(grid: number[][]): number {
    return this.dfs(grid, 0, 0, 0);
  }

  dfs(grid: number[][], r: number, c: number, sum: number): number {
    if (r >= grid.length || c >= grid[0].length) return -1;
    else if (r === grid.length - 1 && c === grid[0].length - 1)
      return sum + grid[r][c];
    else return Math.max(
        this.dfs(grid, r + 1, c, sum + grid[r][c]),
        this.dfs(grid, r, c + 1, sum + grid[r][c]));
  }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  int maxSumDfs(std::vector<std::vector<int>> &grid) {
    return dfs(grid, 0, 0, 0);
  }

private:
  int dfs(std::vector<std::vector<int>> &grid, int r, int c, int sum) {
    if (r >= grid.size() || c >= grid[0].size()) return -1;
    else if (r == grid.size() - 1 && c == grid[0].size() - 1)
      return sum + grid[r][c];
    else return std::max(
        dfs(grid, r + 1, c, sum + grid[r][c]),
        dfs(grid, r, c + 1, sum + grid[r][c]));
  }
};

Go

func MaxSumDfs(grid [][]int) int {
    return dfs(grid, 0, 0, 0)
}

func dfs(grid [][]int, r, c, sum int) int {
    if r >= len(grid) || c >= len(grid[0]) {
        return -1
    } else if r == len(grid)-1 && c == len(grid[0])-1 {
        return sum + grid[r][c]
    } else {
        down := dfs(grid, r+1, c, sum+grid[r][c])
        right := dfs(grid, r, c+1, sum+grid[r][c])
        if down > right {
            return down
        }
        return right
    }
}

Scala

class Solution {
  def maxSumDfs(grid: Array[Array[Int]]): Int = {
    dfs(grid, 0, 0, 0)
  }

  private def dfs(grid: Array[Array[Int]], r: Int, c: Int, sum: Int): Int = {
    if (r >= grid.length || c >= grid(0).length) -1
    else if (r == grid.length - 1 && c == grid(0).length - 1)
      sum + grid(r)(c)
    else Math.max(
      dfs(grid, r + 1, c, sum + grid(r)(c)),
      dfs(grid, r, c + 1, sum + grid(r)(c)))
  }
}

Kotlin

class Solution {
    fun maxSumDfs(grid: Array<IntArray>): Int {
        return dfs(grid, 0, 0, 0)
    }

    private fun dfs(grid: Array<IntArray>, r: Int, c: Int, sum: Int): Int {
        if (r >= grid.size || c >= grid[0].size) return -1
        else if (r == grid.size - 1 && c == grid[0].size - 1)
            return sum + grid[r][c]
        else return maxOf(
            dfs(grid, r + 1, c, sum + grid[r][c]),
            dfs(grid, r, c + 1, sum + grid[r][c]))
    }
}

Swift

class Solution {
    func maxSumDfs(_ grid: [[Int]]) -> Int {
        return dfs(grid, 0, 0, 0)
    }

    private func dfs(_ grid: [[Int]], _ r: Int, _ c: Int, _ sum: Int) -> Int {
        if r >= grid.count || c >= grid[0].count { return -1 }
        else if r == grid.count - 1 && c == grid[0].count - 1 {
            return sum + grid[r][c]
        }
        else { return max(
            dfs(grid, r + 1, c, sum + grid[r][c]),
            dfs(grid, r, c + 1, sum + grid[r][c]))
        }
    }
}

Ruby

class Solution
  def max_sum_dfs(grid)
    dfs(grid, 0, 0, 0)
  end

  def dfs(grid, r, c, sum)
    return -1 if r >= grid.length || c >= grid[0].length
    return sum + grid[r][c] if r == grid.length - 1 && c == grid[0].length - 1
    [dfs(grid, r + 1, c, sum + grid[r][c]), dfs(grid, r, c + 1, sum + grid[r][c])].max
  end
end

Rust

pub struct Solution;

impl Solution {
    pub fn max_sum_dfs(&self, grid: Vec<Vec<i32>>) -> i32 {
        Self::dfs(&grid, 0, 0, 0)
    }

    fn dfs(grid: &Vec<Vec<i32>>, row: i32, col: i32, sum: i32) -> i32 {
        if row >= grid.len() as i32 || col >= grid[0].len() as i32 {
            return -1;
        }
        let r = row as usize;
        let c = col as usize;
        if row == grid.len() as i32 - 1 && col == grid[0].len() as i32 - 1 {
            return sum + grid[r][c];
        }
        Self::dfs(grid, row + 1, col, sum + grid[r][c])
            .max(Self::dfs(grid, row, col + 1, sum + grid[r][c]))
    }
}

Dart

import 'dart:math';

class Solution {
  int maxSumDfs(List<List<int>> grid) {
    return _dfs(grid, 0, 0, 0);
  }

  int _dfs(List<List<int>> grid, int r, int c, int sum) {
    if (r >= grid.length || c >= grid[0].length) return -1;
    else if (r == grid.length - 1 && c == grid[0].length - 1)
      return sum + grid[r][c];
    else return max(
        _dfs(grid, r + 1, c, sum + grid[r][c]),
        _dfs(grid, r, c + 1, sum + grid[r][c]));
  }
}

PHP

class Solution {
    public function maxSumDfs(array $grid): int {
        return $this->dfs($grid, 0, 0, 0);
    }

    private function dfs(array $grid, int $r, int $c, int $sum): int {
        if ($r >= count($grid) || $c >= count($grid[0])) return -1;
        else if ($r === count($grid) - 1 && $c === count($grid[0]) - 1)
            return $sum + $grid[$r][$c];
        else return max(
            $this->dfs($grid, $r + 1, $c, $sum + $grid[$r][$c]),
            $this->dfs($grid, $r, $c + 1, $sum + $grid[$r][$c]));
    }
}

C#

using System;

public class Solution {
    public int MaxSumDfs(int[][] grid) {
        return Dfs(grid, 0, 0, 0);
    }

    private int Dfs(int[][] grid, int r, int c, int sum) {
        if (r >= grid.Length || c >= grid[0].Length) return -1;
        else if (r == grid.Length - 1 && c == grid[0].Length - 1)
            return sum + grid[r][c];
        else return Math.Max(
            Dfs(grid, r + 1, c, sum + grid[r][c]),
            Dfs(grid, r, c + 1, sum + grid[r][c]));
    }
}

Practice Makes Perfect

Grid path problems are a fertile testing ground for recursion and optimization. Once you have this DFS approach solid, try these related problems to build on it:

• Count paths on a board (same movement constraint, but count all paths instead of finding the max sum)
• Maximum sum path with dynamic programming (the efficient version of this problem)
• Minimum sum path in a triangle (similar recursive decomposition on a triangular grid)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. Practicing grid problems with both DFS and DP approaches will give you the flexibility to handle whatever variant shows up in your interview.