class Solution {

public:

int orangesRotting(vector<vector<int>>& grid) {

// figure out the grid size

int n = grid.size();

int m = grid[0].size();

//store {{row,col} , time}

queue<pair<pair<int,int> , int>> q ;

int visited[n][m];

int cntFresh = 0;

for(int i = 0 ; i < n ; i++){

for(int j = 0 ; j < m ; j++){

// if cell contains rotten orange

if(grid[i][j] == 2){

q.push({{i , j} , 0});

// mark as visited (rotten) in visited array

visited[i][j] = 2 ;

}else{

// if not rotten

visited[i][j] = 0;

}

if(grid[i][j] == 1) cntFresh++ ;

}

}

int tm = 0 ;

// delta row and delta column

int delRow[] = {-1 , 0 , 1 , 0};

int delCol[] = {0 , 1 , 0 , -1};

int cnt = 0;

while(!q.empty())

{

int row = q.front().first.first;

int col = q.front().first.second;

int t = q.front().second;

tm = max(tm , t);

q.pop();

//exactly 4 neighbours

for(int i = 0 ; i < 4 ; i++)

{

//look for neighbouring row and column

int nRow = row + delRow[i];

int nCol = col + delCol[i];

// check for valid cell and

//and for unvisited orange

if(nRow < n && nRow >=0 && nCol<m && nCol >=0

&& grid[nRow][nCol] == 1 && visited[nRow][nCol] != 2 )

{

// push in queue with timer increased

q.push({{nRow , nCol} , t + 1 });

// mark as rotten

visited[nRow][nCol] = 2 ;

cnt++ ;

}

}

}

// if all oranges are not rotten

if(cnt != cntFresh) return -1 ;

return tm ;

}

};