Where can I find DSA questions to prepare for the interviews.

Check out . 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.

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 .

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.

Minimum possible modifications in the matrix to reach the destination

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.

1 -> move left
2 -> move right
3 -> move up
4 -> move down.

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:

Input: M = {{2, 2, 4},
{1, 1, 1},
{3, 3, 2}};

Output: 1

Explanation:
Change the value of M[1][2] to 4. Now the path will become
(0, 0) => (0, 1) => (0, 2) => (1, 2) => (2, 2).

Example 2:

Input: M = {{2, 2, 1},
{4, 2, 3},
{4, 3, 2}}

Output: 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:

If the movement of node U is in the direction of V, weight(U, V) = 0,
else weight(U, V) = 1.

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

Implementation

C++ code

#include <bits/stdc++.h>
using namespace std;

int dijkstra(vector<pair<int, int> > *adj, int n, int m, int src, int dest)
{
//A set to store vertices that are being visited.
set<pair<int, int> > visited;

//Vector to store the min distance from the source, initially infinite.
vector<int> distance(n * m, INT_MAX);

//Inserting in a way to keep the vertices sorted along with the distance.
visited.insert({0, src});
distance[src] = 0;

while (!visited.empty()) {
//The first vertex in the set will be at the minimum distance,extract it.
auto temp = *(visited.begin());
visited.erase(visited.begin());

int u = temp.second;

  // getting neighbours
vector<pair<int, int> >::iterator i;
for (i = adj[u].begin();
i != adj[u].end(); ++i) {

// Get the vertex and weight of the current adjacent to u.
int v = (*i).first;
int weight = (*i).second;

if (distance[v] > distance[u] + weight) {
//if the distance of v is not infinite, that means we have already //visited it, but if we get a smaller distance, we will erase it and //insert it with updated distance in the set

if (distance[v] != INT_MAX)
visited.erase(visited.find({ distance[v], v }));

// Updating the distance of v.
distance[v] = distance[u] + weight;
visited.insert(make_pair(distance[v], v));
}
}
}

// Return the distance.
return distance[dest];
}

int MinModifications(vector<vector<int> >& M)
{
int n = M.size();
int m = M[0].size();

// Converting given matrix to a weighted graph.
vector<pair<int, int> > adj[n*m];

for (int i = 0; i =< n-1; i++) {
for (int j = 0; j <= m-1; j++) {
// Each cell in the Mis a node with label i*n + j.

            // adding a node in the graph by going down.
if( i+1 < n){

// if the direction is the same as stated in the given cell, keep the //weight of the edge 0.
  if( M[i][j] == 4)
adj[i * n + j].push_back({(i+1)*n + j, 0 });

  else
adj[i * n + j].push_back({(i+1)*n + j, 1 });
}

// adding a node in the graph by going up.
if( i-1 >= 0){

  if( M[i][j] == 3)
adj[i * n + j].push_back({(i-1)*n + j, 0 });

  else
adj[i * n + j].push_back({(i-1)*n + j, 1 });
}

// going left.
if( j-1 >= 0){
  if( M[i][j] == 1)
adj[i * n + j].push_back({i*n + (j-1), 0 });

  else
adj[i * n + j].push_back({i*n + (j-1), 1 });
}

// going right
if( j+1 < m){
  if( M[i][j] == 2)
adj[i * n + j].push_back({i*n + (j+1), 0 });

  else
adj[i * n + j].push_back({i*n + (j+1), 1 });
}

}
}

// Applying the dijkstra's algorithm
return dijkstra(adj, n, m, 0, (n - 1) * n + m - 1);
}

// Driver code
int main()
{
vector<vector<int> > M = { { 2, 2, 1 },
{ 4, 2, 3 },
{ 4, 3, 2 } };

cout <<"\n "<< MinModifications(M);

return 0;
}

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.

Click here to learn more about 0-1 BFS.

Implementation

C++ code

#include <bits/stdc++.h>
using namespace std;

int zeroOneBFS(vector<pair<int, int> >* adj, int n, int m, int src, int dest,)
{

  // to store the distance.
vector<int> distance( n*m, INT_MAX);

// Double ended queue to do BFS.
deque<int> q;

distance[src] = 0;
q.push_back(src);

while (!q.empty()) {

int u = q.front();
q.pop_front();

for (auto i : adj[u]) {

// Checking for the optimal distance.
if (distance[i.first] > distance[u] + i.second) {
distance[i.first] = distance[u]+ i.second;

//Put 0 weight edges to front and 1 weight edges to back to
//to process vertices in increasing order of weights.
if (i.second == 0)
q.push_front(i.first);
else
q.push_back(i.first);
}
}
}

return distance[dest];
}

int MinModifications(vector<vector<int> >& M)
{
int n = M.size();
int m = M[0].size();

// Converting given matrix to a weighted graph.
vector<pair<int, int> > adj[n*m];

for (int i = 0; i <= n-1; i++) {
for (int j = 0; j <= m-1; j++) {
// Each cell in M is a node with label i*n + j.
// adding a node in the graph by going down.
if( i+1 < n){

// if the direction is the same as stated in the given cell, keep the //weight of the edge 0.
  if( M[i][j] == 4)
adj[i * n + j].push_back({(i+1)*n + j, 0 });

  else
adj[i * n + j].push_back({(i+1)*n + j, 1 });
}

// adding a node in the graph by going up.
if( i-1 >= 0){

  if( M[i][j] == 3)
adj[i * n + j].push_back({(i-1)*n + j, 0 });

  else
adj[i * n + j].push_back({(i-1)*n + j, 1 });
}

// going left.
if( j-1 >= 0){
  if( M[i][j] == 1)
adj[i * n + j].push_back({i*n + (j-1), 0 });

  else
adj[i * n + j].push_back({i*n + (j-1), 1 });
}

// going right
if( j+1 < m){
  if( M[i][j] == 2)
adj[i * n + j].push_back({i*n + (j+1), 0 });

  else
adj[i * n + j].push_back({i*n + (j+1), 1 });
}

}
}

return zeroOneBFS(adj, n, m, 0, (n-1) * n + m - 1);
}

// Driver code
int main()
{
vector<vector<int> > mat = { { 2, 2, 1 },
{ 4, 2, 3 },
{ 4, 3, 2 } };

cout << "\n "<<MinModifications(mat);
return 0;
}

Output

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

Space complexity: O(N * M)

Check out this problem - Matrix Median

FAQs

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.
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.
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:

Both are important graph algorithms. Click here to learn more about graphs.
Apart from that, you can use the Coding Ninjas Studio to practice a wide range of DSA questions asked in lots of interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.