Minimum Cost Path

Given a square grid of size N, each cell of which contains an integer cost that represents a cost to traverse through that cell, we need to find a path from the top left cell to the bottom right cell by which the total cost incurred is minimum.
From the cell (i,j) we can go (i,j-1), (i, j+1), (i-1, j), (i+1, j).  

Examples :

Input: grid = {{9,4,9,9},{6,7,6,4},{8,3,3,7},{7,4,9,10}}
Output: 43
Explanation: The grid is-
9 4 9 9
6 7 6 4
8 3 3 7
7 4 9 10
The minimum cost is-
9 + 4 + 7 + 3 + 3 + 7 + 10 = 43.

Input: grid = {{4,4},{3,7}}
Output: 14
Explanation: The grid is-
4 4
3 7
The minimum cost is- 4 + 3 + 7 = 14.

Expected Time Complexity: O(n²*log(n))
Expected Auxiliary Space: O(n²) 
 Constraints:
1 ≤ n ≤ 500
1 ≤ cost of cells ≤ 500

Approach 01:

Time Complexity

• Initialization and Traversal:

  The solution involves a nested loop to initialize the minCostGrid and compute the minimum cost path. The outer loop iterates over each row numRows, and the inner loop iterates over each column numCols. Thus, the total time complexity for this part is \( O(\text{numRows} \times \text{numCols}) \).

• Cost Update via Four Directions:

  Another nested loop is used to update the cell costs by considering all four directions (up, down, left, right). The loops iterate again over every cell in the grid, resulting in a time complexity of \( O(\text{numRows} \times \text{numCols}) \).

• Overall Time Complexity:

  The overall time complexity is \( O(\text{numRows} \times \text{numCols}) \), as both steps have the same time complexity and are performed sequentially.

Space Complexity

• Space for the Minimum Cost Grid:

  The solution uses an additional 2D vector minCostGrid of size numRows x numCols to store the minimum cost to reach each cell. Thus, the space complexity for this is \( O(\text{numRows} \times \text{numCols}) \).

• Overall Space Complexity:

  The overall space complexity is \( O(\text{numRows} \times \text{numCols}) \), primarily due to the space required for the minCostGrid array.