[Why reinvent the wheel??] An easy understood commented solution based on trapping rain 1


  • 9
    /*
    Basic physics:
    Unlike bricks, water flows to wherever it could. 
    i.e we can't have the follwoing config made with water, but can do it with bricks
    000
    010
    000
    In the case above, if the "1" is built with water, that water can't stay. It needs to be spilled!
    
    2 steps Algorithm: 
    1. Since we know how to trap rain water in 1d, we can just transfor this 2D problem into 2 1D problems
        we go row by row, to calculate each spot's water
        we go column by column, to calculate each spot's water
    
    2. Then, here comes the meat,
        For every spot that gets wet, from either row or column calculation, the water can possibly spill.
        We need to check the water height aganist it's 4 neighbors. 
            If the water height is taller than any one of its 4 neightbors, we need to spill the extra water.
            If we spill any water from any slot, then its 4 neightbors needs to check themselves again.
                For example, if we spill some water in the current slot b/c its bottm neighbor's height, current slot's top neighbor's height might need to be updated again.
            we keep checking until there is no water to be spilled.
    */
    
    
    public class Solution {
        public int trapRainWater(int[][] heightMap) {
            /*FIRST STEP*/
            if(heightMap.length == 0) return 0;
            int[][] wetMap = new int[heightMap.length][heightMap[0].length];
            int sum = 0;
            /*row by row*/
            for(int i = 1; i < wetMap.length - 1; i++){
                wetMap[i] = calculate(heightMap[i]);
            }
            /*column by column*/
            for(int i = 1; i < heightMap[0].length - 1; i++){
                int[] col = new int[heightMap.length];
                for(int j = 0; j < heightMap.length; j++){
                    col[j] = heightMap[j][i];
                }
                int[] colResult = calculate(col);
                /*update the wetMap to be the bigger value between row and col, later we can spill, don't worry*/
                for(int j = 0; j < heightMap.length; j++){
                    wetMap[j][i] = Math.max(colResult[j], wetMap[j][i]);
                    sum += wetMap[j][i];
                }
            }
            /*SECOND STEP*/
            boolean spillWater = true;
            int[] rowOffset = {-1,1,0,0};
            int[] colOffset = {0,0,1,-1};
            while(spillWater){
                spillWater = false;
                for(int i = 1; i < heightMap.length - 1; i++){
                    for(int j = 1; j < heightMap[0].length - 1; j++){
                        /*If this slot has ever gotten wet, exammine its 4 neightbors*/
                        if(wetMap[i][j] != 0){
                            for(int m = 0; m < 4; m++){
                                int neighborRow = i + rowOffset[m];
                                int neighborCol = j + colOffset[m];
                                int currentHeight = wetMap[i][j] + heightMap[i][j];
                                int neighborHeight = wetMap[neighborRow][neighborCol] + 
                                                                  heightMap[neighborRow][neighborCol];
                                if(currentHeight > neighborHeight){
                                    int spilledWater = currentHeight - Math.max(neighborHeight, heightMap[i][j]);
                                    wetMap[i][j] = Math.max(0, wetMap[i][j] - spilledWater);
                                    sum -= spilledWater;
                                    spillWater = true;
                                }
                            }    
                        }    
                    }
                }
            }
            return sum;
        }
        
        /*Nothing interesting here, the same function for trapping water 1*/
        private int[] calculate (int[] height){
            int[] result = new int[height.length];
            Stack<Integer> s = new Stack<Integer>();
            int index = 0;
            while(index < height.length){
                if(s.isEmpty() || height[index] <= height[s.peek()]){
                    s.push(index++);
                }else{
                    int bottom = s.pop();
                    if(s.size() != 0){
                        for(int i = s.peek() + 1; i < index; i++){
                            result[i] += (Math.min(height[s.peek()], height[index]) - height[bottom]);
                        }    
                    }
                }
            }
            return result;
        }   
        
    }
    

  • 0
    Q

    In the second round of calculating wetMap, why do you choose the max of (row result, column result)? What if you choose min of the two? I tested your code with Min and it still passes.


  • -1

    @quesder Good question. Both min and max should work. (I had the same question as you before, so I tried both. Both are accepted)
    If we take min there, we are already spilling some water during step1.
    I just want to make the 2 steps doing their own job, i.e first step only calculate which slot can possibly hold water, second step spills all the extra water.


  • 0
    Q

    @DonaldTrump The main stream solution uses priority queue and is supposed to run in O(rc log(rc) ) time. Your solution is about rc * 4 * (2 or 3) . How come the main stream solution is 99 ms and yours is 483 ms. Do I analyze wrongly?


  • 12

    @quesder said in [Why reinvent the wheel??] An easy understood commented solution based on trapping rain 1:

    Do I analyze wrongly?

    Quite a bit, yes. Even the first step isn't O(rc) but only O(rc(r+c)), because he uses a quadratic time algorithm for the 1D problem. And the second step is only O((rc)^2). I don't get 483 ms for it, though, only about 160 ms.

    Don't know how this got upvotes, I think it's pretty bad. Not just because of the poor complexity and the large code size, but also because it proclaims "Why reinvent the wheel??" as if the other solutions had done that and this one hadn't, and the wetMap[i][j] = Math.max(0, wetMap[i][j] - spilledWater); instead of wetMap[i][j] -= spilledWater; making me think he doesn't know what he's doing, and the "Nothing interesting here" trying to keep people from looking closely and seeing the quadratic complexity. I guess he simply successfully managed to fool some people, just like in his election campaign :-)


  • -1

    Thanks for the input. However I'd like to response to you comment.

    @StefanPochmann said in [Why reinvent the wheel??] An easy understood commented solution based on trapping rain 1:

    Don't know how this got upvotes, I think it's pretty bad. Not just because of the poor complexity and the large code size,

    For poor complexity, I agree this is not as fast as the priority queue solution, but I don't think I mentioned this solution is necessarily the fastest one. Also not sure why do you think my 1D calculation is a quadratic complexity function?

    For large code size, I compared mine against couple other posts, don't think the length of actual code chunk differs very much.
    After all, I personally prefer people sharing both thinking process and the implementation, not just something like a "5 line solution" and then 0 comment, saying read yourself or you are dumb.
    Readability is a very important aspect of the code if you have ever worked with other people. I think sharing algorithm design methodology is more helpful than the actual implementation here.

    but also because it proclaims "Why reinvent the wheel??" as if the other solutions had done that and this one hadn't,

    Not really. It's the flip side. I think this solution have utilized the solution from 1D question that other solutions hadn't. Again, I'm not saying this is necessarily the fastest solution.

    the "Nothing interesting here" trying to keep people from looking closely and seeing the quadratic complexity.

    This is just your opinion. My intention was to make my solution more understandable without overwhelming people with too many code. If they know how to do 1D trapping water, they can simply skip that part.

    I guess he simply successfully managed to fool some people, just like in his election campaign :-)

    Not sure what I'm fool people into? Into up voting? Maybe this somewhat not fastest solution is more easily understood?


  • 6

    @DonaldTrump said in [Why reinvent the wheel??] An easy understood commented solution based on trapping rain 1:

    Not sure what I'm fool people into? Into up voting?

    Yes, just like you're doing in politics :-). There are really a lot of similarities between you here and you there.

    the "Nothing interesting here" trying to keep people from looking closely and seeing the quadratic complexity.

    This is just your opinion.

    No, that's not my opinion. I just made that up to fit my narrative :-P. Fits very well, though, and came quite naturally. Anyway, given what I've seen of you on TV I'm sure you appreciate stuff being made up.

    Maybe this somewhat not fastest solution is more easily understood?

    Maybe. Then again, it really seems even you yourself don't fully understand it. Like already mentioned, wetMap[i][j] = Math.max(0, wetMap[i][j] - spilledWater); should simply be wetMap[i][j] -= spilledWater;, after all you already capped spilledWater appropriately and you also already do simply sum -= spilledWater; in the very next line. Also, taking the max in the first step instead of the min (as pointed out by quesder) doesn't inspire confidence.

    I think this solution have utilized the solution from 1D question that other solutions hadn't.

    Well, other solutions don't need it. They're not reinventing the wheel. They're building a boat. Boats don't have wheels. And your solution also doesn't utilize it much. Like you said yourself, "the meat" of your solution is the second part, that's where the real work is done. It's not like you're using the 1D solution to do the work. You can btw even replace your whole first step with the following and then the solution gets accepted in less time, about 110ms instead of your 160ms.

    int[][] wetMap = new int[heightMap.length][heightMap[0].length];
    int sum = 0;
    for(int i = 1; i < wetMap.length - 1; i++)
        for(int j = 1; j < wetMap[i].length - 1; j++)
            sum += wetMap[i][j] = 1000000000;
    

    why do you think my 1D calculation is a quadratic complexity function?

    Because I read it, understood it, and then confirmed it with tests just to be sure.

    Consider inputs like {1000, 999, 998, ..., 3, 2, 1, 1000}, which causes your result[i] += ... to be executed 499500 times.


  • 2

    Hands down. So far the best solution.
    ["Why reinvent the wheel??"]
    I totally agree with you, Mr. Trump. I worked very hard to understand Trapping Rain 1 and spent considerable time to code by myself. I know my hard work will be paid off because of your brilliant algorithm.

    I copy-pasted your code but replaced the Trapping Rain 1 part with my own one. I was so thrilled when I hit the submit button because I was like 'oh my lord! Trump's code and my code are gonna compiled together!' Then it happened, 48/48 tests passed.

    Though I only contribute 20%ish of the code which was proved to be successful, it really makes me believe that Mr. Trump will make America great again.

    I up voted.


  • 1

    @TrumpFanBoy Thanks for the support.
    However I do want to mention @StefanPochmann has a good point in his last post.

    We don't have to use the solution from trap rain 1. My spill water(step 2) is already good enough by itself. Instead, we can do what @StefanPochmann mentioned by adding an arbitrarily big number to all the inner slots, and let the water spill. (This big number shouldn't be too big to cause us integer overflow issue)

    In this way, we can shorten the solution to the following:

    public class Solution {
        public int trapRainWater(int[][] heightMap) {
            if(heightMap.length == 0) return 0;
            int[][] wetMap = new int[heightMap.length][heightMap[0].length];
            int sum = 0;
    
            /*Step 1, Make it rain.
              We add a big number to simulate that we had a heavy rain*/
            for(int i = 1; i < wetMap.length - 1; i++){
                for(int j = 1; j < wetMap[i].length - 1; j++){
                    sum += wetMap[i][j] = 1000000000;
                }
            }
            /*step 2, spill the extra water*/
            boolean spillWater = true;
            int[] rowOffset = {-1,1,0,0};
            int[] colOffset = {0,0,1,-1};
            while(spillWater){
                spillWater = false;
                for(int i = 1; i < heightMap.length - 1; i++){
                    for(int j = 1; j < heightMap[0].length - 1; j++){
                        if(wetMap[i][j] != 0){
                            for(int m = 0; m < 4; m++){
                                int neighborRow = i + rowOffset[m];
                                int neighborCol = j + colOffset[m];
                                int currentHeight = wetMap[i][j] + heightMap[i][j];
                                int neighborHeight = wetMap[neighborRow][neighborCol] + heightMap[neighborRow][neighborCol];
                                if(currentHeight > neighborHeight){
                                    int spilledWater = currentHeight - Math.max(neighborHeight, heightMap[i][j]);
                                    wetMap[i][j] = wetMap[i][j] - spilledWater;
                                    sum -= spilledWater;
                                    spillWater = true;
                                }
                            }    
                        }    
                    }
                }
            }
            return sum;
        }
    }
    

    Anyway thanks for the input from both of you. Let's make Leetcode greater again and again.


  • 15

    Thanks for making Trapping Rain Water 1 great again.


  • 1
    J

    @DonaldTrump said in [Why reinvent the wheel??] An easy understood commented solution based on trapping rain 1:

    ou. Let's make Leetcode greater again

    Actually, I think the priority_queue solution is using the wheel.
    For 1d problem, there is a different way, just 2 pointers. Every time, deal the smaller of left and right with its neighbors, then continue with smaller.
    For 2d problem, it is the same. Get the smallest one of all boundaries, deal it with neighbors, then continue with smallest.
    Don't you think they are the same?


  • 3
    O

    President Trump and his "fanboy" made me laugh out loud because their acting is so fun to watch. No offense. Just pure fun.

    I agree with @StefanPochmann that this solution does not at all depend on 42 Trapping Rain Water, so the title is improper.

    I don't think the 2nd part is bad, either. It's not optimal, but it reminds me of 417 Pacific Atlantic Water Flow.


  • 0
    Z

    @StefanPochmann The complexity is bad. I tried to implement this solution in Python, and it even cannot pass all test cases in time limit. Much worse than the priority queue / heap solution.


Log in to reply
 

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