Two Pass Solution O(n)


  • 0
    S

    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>();
    res.Add(n);

                for (int j = 0; j < matrix[i].Count; j++)
                {
                    if (matrix[i][j] == 0)
                    {
                        n.Add(0);
                    }
                    else
                    {
                        n.Add(int.MaxValue);
    
                        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;
    

    ...


  • 0
    Y
    This post is deleted!

Log in to reply
 

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