Minimum Passes Of Matrix

• Time : O(nm)
• Space : O(n+m)

int minimumPassesOfMatrix(vector<vector<int>> matrix) {
  int neg = 0, res = 0;
	int n = matrix.size(), m = matrix[0].size();
	int dy[4]{-1,0,1,0},dx[4]{0,1,0,-1};
	queue<pair<int,int>> q;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(matrix[i][j] < 0) neg++;
			else if(matrix[i][j] > 0) q.push({i,j});
		}
	}
	for(; !q.empty() and neg; res++) {
		int sz = q.size();
		while(sz--) {
			auto [y, x] = q.front(); q.pop();
			for(int i = 0; i < 4; i++) {
				int ny = y + dy[i], nx = x + dx[i];
				if(0 <= ny and ny < n and 0 <= nx and nx < m and matrix[ny][nx] < 0) {
					neg--;
					matrix[ny][nx] *= -1;
					q.push({ny,nx});
				}
			}
		}
	}
	
  return neg ? -1 : res;
}