Need help. I am unable to understand why output is not matching...I have used very simple approach...Thanks in advance.


  • 0
    A

    Explanation: I am using four matrix to keep track of max height in all directions...and if height of current point is less than min of all direction matrices..then I am adding the difference in total amount of water.

    public int TrapRainWater(int[,] heightMap)
    {
    int r = heightMap.GetLength(0);
    int c = heightMap.GetLength(1);
    int[,] leftMap = new int[r, c];
    int[,] rightMap = new int[r, c];
    int[,] topMap = new int[r, c];
    int[,] bottomMap = new int[r, c];

            for (int i = 0; i < r; i++)
            {
                leftMap[i, 0] = heightMap[i, 0];
                for (int j = 1; j < c; j++)
                {
                    if (heightMap[i, j] < leftMap[i, j - 1]) leftMap[i, j] = leftMap[i, j - 1];
                    else leftMap[i, j] = heightMap[i, j];
                }
            }
            for (int i = 0; i < r; i++)
            {
                rightMap[i, c - 1] = heightMap[i, c - 1];
                for (int j = c - 2; j >= 0; j--)
                {
                    if (heightMap[i, j] < rightMap[i, j + 1]) rightMap[i, j] = rightMap[i, j + 1];
                    else rightMap[i, j] = heightMap[i, j];
                }
            }
    
            for (int j = 0; j < c; j++)
            {
                topMap[0, j] = heightMap[0, j];
                for (int i = 1; i < r; i++)
                {
                    if (heightMap[i, j] < topMap[i - 1, j]) topMap[i, j] = topMap[i - 1, j];
                    else topMap[i, j] = heightMap[i, j];
                }
            }
    
            for (int j = 0; j < c; j++)
            {
                bottomMap[r - 1, j] = heightMap[r - 1, j];
                for (int i = r - 2; i >= 0; i--)
                {
                    if (heightMap[i, j] < bottomMap[i + 1, j]) bottomMap[i, j] = bottomMap[i + 1, j];
                    else bottomMap[i, j] = heightMap[i, j];
                }
            }
    
            int totalAmount = 0;
            for (int i = 1; i < r - 1; i++)
            {
                for (int j = 1; j < c - 1; j++)
                {
                    int min = Math.Min(Math.Min(leftMap[i, j], rightMap[i, j]), Math.Min(topMap[i, j], bottomMap[i, j]));
                    if (min > heightMap[i, j])
                        totalAmount += min - heightMap[i, j];
                }
            }
            return totalAmount;
        }
    

    Inputs: [[12,13,1,12],[13,4,13,12],[13,8,10,12],[12,13,12,12],[13,13,13,13]]
    My output = 15;
    Expected output =14;


  • 0
    H

    Were you able to find out the reason?


  • 0
    H

    I found out the reason. See (1, 1). By your algorithm, it will be 9 at that slot while it should be 8.


  • 0
    W

    Why would (1,1) by 8. 9 seems like the correct value to me since 9 units of water gets trapped at (1,1) between the walls (1,0), (0,1), (1,2), (3,1). Each of these walls are 13 units tall, so (13-4)=9 units of water should get trapped there.
    What am I missing?


  • 0
    Z

    Because the wall's height is 12 instead of 13. And the bottom here is already 4 unit height, so it should be 8 waters


  • 0
    J

    @zhou.yu.505

    12 13 1 12
    13 4 13 12
    13 8 10 12
    12 13 12 12
    13 13 13 13

    For (1,1), its up wall is (0,1) whose value is 13, down wall is (3,1) whose value is 13, left wall is (1,0) whose value is 13 while right wall is (1,2) whose value is 13.

    Now that you mention 12, do you actually mean its right wall should be (1,3)? But I think (1,2) is higher than (1,3).


  • 0
    H

    @zhou.yu.505 can you explain to me why the wall for [1][1] is 12? still think it should be 13,what am I missing?


  • 0
    Z

    @hanyuliu123
    Thank you notifying me here.

    The table of case is here. Thanks to @yuanxu
    12 13 1 12
    13 4 13 12
    13 8 10 12
    12 13 12 12
    13 13 13 13

    We are only trapping rain water expect the edges which is the following sub-table:
    4 13
    8 10
    13 12

    The bottom of rain container should be 4,8,10 obviously. Which means the edges of this container is the following:(Please ignore the bottoms that I added to this sub-table, they are good for the understanding.)
    __13
    13 4 13
    13 8 10 12
    __13 12

    According to the edges of container, you can see the shortest edge is 12 height which is the height of container:
    __12
    12 4 12
    12 8 10 12
    __12 12

    As a result, the final output should be 8+4+2 which is 14 instead of 15.

    If you want to know more, just feel free to let me know. @hanyuliu123 @yuanxu


Log in to reply
 

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