2328. Number of Increasing Paths in a Grid

Leetcode

📝 Problem Details

• Title: 2328. Number of Increasing Paths in a Grid
• Link: https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/
• Difficulty: Hard
• Tags/Categories: Dynamic-Programming Memoization DFS Arrays Matrix Graphs

💭What Were My Initial Thoughts?

- DFS that recursively stores growing / increasing paths incrementally into a paths vector
- restart the path when curr > next node 
- return the size of the paths vector

🤔What Did I Struggle With?

- formulating my "restarting of a new path"
	- each DFS call can be implicitly thought of as a new path without needing to separate restart logic
- having a paths vector is too computationally inefficient if the grid is large
	- directly counting the number of paths during DFS is the correct approach

💡 Explanation of Solution

1. Memo Table
	- the memo table is initialized to -1 to indicate uncomputed cells
	- memo[i][j] stores thte total number of increasing paths starting from cell (i,j)

2. MOD Value
	- since the input can be very large, paths are computed modulo 10^9 + 7 to avoid integer overflow

3. DFS Logic:
	- explore all four directions from the current cell
	- only move to a neighbouring cell if its value is greater than the current cell (ensures strictly increasing)

4. Final Calculation
	- after performing DFS for all cells, the sym of all values in the memo table gives the tital number of increasing paths

⌛ Complexity Analysis

Time Complexity: O(m * n)
	DFS Exploration:
	- each cell (i,j) in the grid is visited once during the DFS call for that cell
	- during each DFS call, we explore up to 4 possible directions
	- the exploration is bound byt he size of the grid
	- an additional constraint that the neighbouring values must be strictly increasing
	- each cell is processed at constant time O(1) for all its neighbours

Space Complexity: O(m * n)
- the memo table stores a value for each cell

💻 Implementation of Solution

class Solution {
public:
	int MOD = 1e9 + 7;
	vector<vector<int>> directions = { //right, down, left, up
		{0,1}, //move right by keeping the row the same and increasing the column
		{1,0}, //move down by increasing the row and keeping the column the same
		{0,-1}, // move left by keeping the row the same and decreasing the column
		{-1,0} // move up by decreasing the row and keeping the column the same 
	};
 
	int dfs(int i, int j, vector<vector<int>>& grid vector<vector<int>>& memo) {
		if(memo[i][j] != -1) return memo[i][j]; // return cached result
 
		memo[i][j] = 1; // each cell is a path of length 1
 
		for(auto& dir : directions) {
			int x = i + dir[0], y = j + dir[1];
 
			/*
				x >= 0 && x < grid.size() : making sure row index is within bounds
				y >= 0 && y < grid[0].size() : making sure col index is within bounds
				grid[x][y] > grid[i][j] : cell's value is strictly increasing
			*/
			if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] > grid[i][j]) {
				memo[i][j] = (memo[i][j] + dfs(x, y, grid, memo)) % MOD; 
			}
		}
		return memo[i][j];
	}
	
	int countPaths(vector<vector<int>>& grid) {
		int rows = grid.size(), cols = grid[0].size();
		vector<vector<int>> memo(rows, vector<int>(cols, -1)); // memoization table
		int totalPaths = 0;
 
		for(int i=0; i < rows; i++) {
			for(int j=0; j < cols; j++) {
				totalPaths = (totalPaths + dfs(i, j, grid, memo)) % MOD;
			}
		}
		return totalPaths;
	}
};