# Two Pass Solution O(n)

• first pass take care of left and up
second pass right and down
...
IList<IList<int>> res;
public IList<IList<int>> UpdateMatrix(IList<IList<int>> matrix)
{
res = new List<IList<int>>();
for (int i = 0; i < matrix.Count; i++)
{
List<int> n = new List<int>();

``````            for (int j = 0; j < matrix[i].Count; j++)
{
if (matrix[i][j] == 0)
{
}
else
{

if (i > 0 && res[i - 1][j] != int.MaxValue && res[i][j] > res[i - 1][j] + 1)
res[i][j] = res[i - 1][j] + 1;

if (j > 0 && res[i][j - 1] != int.MaxValue && res[i][j] > res[i][j - 1] + 1)
res[i][j] = res[i][j - 1] + 1;
}

}
}

for (int i = matrix.Count - 1; i >= 0; i--)
{
for (int j = matrix[i].Count - 1; j >= 0; j--)
{
if (res[i][j] != 0)
{
if (i < matrix.Count - 1 && res[i][j] > res[i + 1][j] + 1)
res[i][j] = res[i + 1][j] + 1;

if (j < matrix[i].Count - 1 && res[i][j] > res[i][j + 1] + 1)
res[i][j] = res[i][j + 1] + 1;
}
}
}

return res;
``````

...

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.