Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
3.
BFS
3.1.
Input
3.2.
Output
3.3.
Time Complexity 
3.4.
Space Complexity 
4.
Dynamic Programming
4.1.
Input
4.2.
Output
4.3.
Time Complexity 
4.4.
Space Complexity 
5.
Key Takeaways
Last Updated: Mar 27, 2024

01 Matrix

Author Saksham Gupta
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

BFS is generally the second most asked topic in interviews after DP. DP and BFS are surely hard to master, and difficulty arises when both of them are combined. But you don’t have to worry as Ninja is here to help you. Thus to strengthen your concepts around these topics we’ll see one such question that involves both of these, i.e., 01 matrix.

Understanding the Problem

The problem is fairly simple to understand. We have been given a binary matrix, i.e., it contains only 0 and 1. Our task is to find the distance of the nearest 0 for every cell.

Let’s look at an example to have a better understanding of the problem.

0

1

1

0

1

1

0

1

1

 

The output for the above matrix would be

0

1

2

0

1

2

0

1

2

 

As for cells ((0, 0), (1, 0), (2, 0)) minimum distance from zeros is 0 as they themselves are zero. For cells((0, 1), (1, 1), (2, 1)) minimum distance from zero is 1 as they have a zero to their left, which is only cell apart (distance 1). Similarly, for the remaining cells, the distance is 2 (2 cells apart).

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

BFS

Intuition for the BFS is straightforward. We’ll perform BFS in the matrix. For this, we will first mark visited and unvisited cells. We will mark visited cells with 0 (Also, cells that contain 0 will be marked as zero as that is the minimum distance to other 0, and there is no need to visit them). Thus, cells containing 0 will be pushed in the queue as well as they are now visited, and cells containing 1 will be marked as -1. Now we will perform BFS until the queue is empty. We will pop an element from the queue (basically index of a cell) and will check for its adjacent elements. If it’s out of the boundary or if it’s visited, e’ll skip it. Otherwise, we will update it with the value of the current element (value at the cell that is popped) + 1. 

 

Now things will become more clear from the code.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

    // To perform a search in adjacent directions.
    vector<int> DIR = { 0, 1, 0, - 1, 0};

    // Queue to perform BFS.
    queue<pair<int, int> > q;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            // If 0, then we can mark it as visited.
            if (mat[i][j] == 0)
            {
                q.push({i, j});
            }

            // Not visited.
            else
                mat[i][j] = - 1;
    }

    while (q.size() != 0)
    {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            // Checking if it's within the boundary.
            int nr = r + DIR[i], nc = c + DIR[i + 1];
            if (nr < 0 || nr == m || nc < 0 || nc == n || mat[nr][nc] != - 1)
                continue;

            // Updating value according to the algorithm.
            mat[nr][nc] = mat[r][c] + 1;
            q.push({nr, nc});
        }
    }
    return mat;
}

int main()
{
    // Taking user input.
    int m, n;
    cin >> m >> n;
    vector<vector< int> > matrix(m, vector<int>(n, 0));

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> matrix[i][j];
        }
    }

    // Calling the function, 'updateMatrix()'.
    matrix = updateMatrix(matrix);

    // Printing the final matrix.
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << matrix[i][j] << " ";
        }
        cout << '\n';
    }
    return 0;
}

Input

3 3
0 1 1
0 1 1
0 1 1

Output

0 1 2
0 1 2
0 1 2

Time Complexity 

O(M * N), where ‘M’ is the number of rows and ‘N’ is the number of columns in the matrix.

As we are traversing each element in the matrix only once and there are M * N elements in the matrix, the time complexity is O(M * N)

Space Complexity 

O(M * N), where ‘M’ is the number of rows and ‘N’ is the number of columns in the matrix.

This is because we are using an extra queue to perform BFS which will store a total of M * N elements. Thus taking the space complexity to O(M * N).

Now we are using extra space for the queue to perform BFS, and we surely can reduce it by performing in-place operations. But how? Let’s see.

Dynamic Programming

Now for DP, we will make use of cells that are being already processed, so we will not pick up cells containing ‘0’ as they can be initialized to 0 (which means they are visited). But how are we going to DP here?

We know that adjacent cells account for only 4 directions, i.e., top, bottom, left, and right; thus, we can divide the problem into two parts.

  • In the first part, we will move only 2 directions which are left and top. Then we iterate cells from top to bottom, and from left to right, Basically, we will only calculate the distance of a cell-based only on its left and top neighbors.
  • In the second part, we will move only 2 directions which are right and bottom. Then, we iterate cells from bottom to top, and from right to left, Basically, we will update the distance of a cell-based only on its right and bottom neighbors.

Finally, we can club the answer from both the steps to reach our final answer.

Refer to the following image for a better understanding.

 

We can see that in the first image we are computing distance from the cell’s top and left neighbors.

Whereas in the second image we are computing distance from a cell’s bottom and right neighbors.

 

Now things will become more clear from the code.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector< int> > updateMatrix(vector<vector< int> > &mat)
{
    // The distance of cells is up to (M+N)
    int m = mat.size(), n = mat[0].size(), boundary = m + n;

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // If it''s visited, then skip.
            if (mat[i][j] == 0)
                continue;

            // Initializing with maximum possible value.
            int top = m + n, left = m + n;

            // If it's within boundaries.
            if (j - 1 >= 0)
                left = mat[i][j - 1];
            if (i - 1 >= 0)
                top = mat[i - 1][j];

            // Filling the minimum value out of the two directions.
            mat[i][j] = min(top, left) + 1;
        }
    }

    for (int i = m - 1; i >= 0; i--)
    {
        for (int j = n - 1; j >= 0; j--)
        {
            // If it's visited, then skip.
            if (mat[i][j] == 0)
                continue;

            // Initializing with maximum possible value.
            int bottom = m + n, right = m + n;

            // If it's. Close within boundaries.
            if (i + 1 < m)
                bottom = mat[i + 1][j];
            if (j + 1 < n)
                right = mat[i][j + 1];

            // Filling the minimum value out of the two directions.
            mat[i][j] = min(mat[i][j], min(bottom, right) + 1);
        }
    }

    return mat;
}

int main()
{
    // Taking user input
    int m, n;
    cin >> m >> n;
    vector<vector< int> > matrix(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> matrix[i][j];
        }
    }

    // Calling the function, 'updateMatrix()'.
    matrix = updateMatrix(matrix);

    // Printing the final matrix.
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << matrix[i][j] << “ “;
        }
                   cout << ‘\n’;
    }

    return 0;
}

Input

3 3
0 1 1
0 1 1
0 1 1

Output

0 1 2
0 1 2
0 1 2

Time Complexity 

O(M * N), where ‘M’ is the number of rows and ‘N’ is the number of columns in the matrix.

As we are traversing each element in the matrix once, and there are M * N elements in the matrix. Thus we will be traversing over a total of M * N elements and therefore the complexity is O(M * N).

Space Complexity 

O(1).

We are not using any extra space.

Key Takeaways

We saw how we solved the problem 0 1 matrix from BFS and then optimized it using DP. Now, understanding a new concept always makes one excited, and this excitement leads to learning more concepts. We are here to help you with that too. Close your eyes and click on Coding Ninjas Studio to practice top problems like 01 matrix, Set Matrix zerosattempt mock testsread interview experiences, and many more. Till then, Happy Coding!

Previous article
0-1 BFS
Next article
Topological sort without Kahn’s algorithm
Live masterclass