1.
Question
2.
Solution
2.1.
Method 1
2.2.
Method 2
3.
FAQs
4.
Key takeaways
Last Updated: Mar 27, 2024

# Minimum possible modifications in the matrix to reach the destination

GAZAL ARORA
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Question

Given a matrix M of size NxM with integer values 1,2,3, and 4, each value represents the only possible movement from that cell.

Return minimum possible changes required in the matrix such that a path exists from (0, 0) to (N-1, M-1).

Alert Ninjas:  Donâ€™t stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide.

Example 1:

Example 2:

## Solution

### Method 1

Consider each cell of the 2D matrix to be a node in the weighted graph, with each node having a maximum of four connected nodes (possible four directions). Each edge weights as follows:

Now, the problem reduces to finding the shortest path in a weighted graph, which can be computed using Djikstraâ€™s Algorithm.

Implementation

C++ code

Output

Time Complexity: O( N * M * log( N * M ) )

Space Complexity: O( N * M )

### Method 2

Reduce the given problem to find the shortest path in a weighted graph as done in method 1. Now, edge weights are 0 and 1 only, i.e., a 0-1 graph. The shortest path in 0-1 graphs can be found using 0-1 BFS.

Implementation

C++ code

Output

Time complexity from this method: O(N * M)

Space complexity: O(N * M)

Check out this problem - Matrix Median

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## FAQs

1. Where can I find DSA questions to prepare for the interviews.
Check out Coding Ninjas Studio. It is the best platform to prepare for coding interviews. You will find a variety of questions and interview experiences of top companies. You can also participate in the contests and get a chance to win amazing prizes.

2. How do you find the minimum cost of the path.
The path to reach the destination cell(m, n) must be through one of the 3 cells: (m-1, n) / (m, n-1) or (m-1, n-1). So the minimum cost to reach the destination will be â€śminimum of the 3 cells plus cost[m][n]â€ť.
You can practice the question here.

3. How do you find the shortest path in a matrix?
The idea is to apply BFS (breadth-first search)You can only apply the BFS in an unweighted graph. Store each cell of the matrix as a node with their row no., column no., and distance from the source cell. Start BFS with the source cell.

## Key takeaways

This article reduces a matrix problem to a graph problem where we have to find the shortest path in a weighted graph. We solved this problem using two approaches: