Given An M*N grid with colors
[[1,1,2],
[1,2,1],
[2,1,1]]
Starting from [0,0] paint all the corodiantes of the same color if not blocked by some other color
eg given
[[1,1,2],
[1,2,1],
[2,1,1]] and color to change to is 3

Then result is
[[3,3,2],
[3,2,1],
[2,1,1]]

The coordinates at [1,2],[2,1],[2,2] are not changed because the other color 2 is blocking them from getting changed. As the adjacent elements are only horizontally or vertically adjacent but not diagonal adjacent.

For this problem, i gave below BFS approach and while calculating Sapce complexity, the interviewer was stressing on exact sapace complexity even though i gave him space complexity as O(M*N)

Can someone please help me analyze the exact sapace complexity of the problem. He is not satisfied with O(M*N)

 void paint(int grid[][],int targetColor){
 if(grid == null || grid.length == 0) return;
 Queue<int[]> q = new LinkedList<>();
 HashSet<String> seen = new HashSet<>();
 int currentColor = grid[0][0];
 q.add(new int[]{0,0});
 seen.add(0 + "|" + 0);
 int dirs[][] = {{0,1},{0,-1},{1,0},{-1,0}};
 while(!q.isEmpty()){
	 int current[] = q.poll(), i = current[0],j = current[1];
	 for(int dir:dirs){
		 int ni = i + dir[0];
		 int nj = j + dir[1];
		 if(ni >=0 && ni < N && nj >=0 && nj < M && !seen.contains(ni + "|" + nj) && grid[ni][nj] == currentColor){
			 seen.add(ni + "|" + nj);
			 grid[ni][nj] = targetColor;
			 q.add(new int[]{ni,nj});
		 }
	 }
 }
 return;
 }