7 lines C / C++


  • 103

    Keep track of the already safe level and the total water so far. In each step, process and discard the lower one of the leftmost or rightmost elevation.


    C

    Changing the given parameters to discard the lower border. I'm quite fond of this one.

    int trap(int* height, int n) {
        int level = 0, water = 0;
        while (n--) {
            int lower = *height < height[n] ? *height++ : height[n];
            if (lower > level) level = lower;
            water += level - lower;
        }
        return water;
    }
    

    Slight variation with two pointers (left and right).

    int trap(int* height, int n) {
        int *L = height, *R = L+n-1, level = 0, water = 0;
        while (L < R) {
            int lower = *L < *R ? *L++ : *R--;
            if (lower > level) level = lower;
            water += level - lower;
        }
        return water;
    }
    

    C++

    With left and right index.

    int trap(vector<int>& height) {
        int l = 0, r = height.size()-1, level = 0, water = 0;
        while (l < r) {
            int lower = height[height[l] < height[r] ? l++ : r--];
            level = max(level, lower);
            water += level - lower;
        }
        return water;
    }
    

    With left and right iterator.

    int trap(vector<int>& height) {
        auto l = height.begin(), r = height.end() - 1;
        int level = 0, water = 0;
        while (l != r + 1) {
            int lower = *l < *r ? *l++ : *r--;
            level = max(level, lower);
            water += level - lower;
        }
        return water;
    }

  • 7

    Your code and idea are really fabulous to me. Thank you for your solution sharing.


  • 0
    C

    smart coder~


  • 0

    It will be better, level = 0 => level=INT_MIN, so that negative value is also applied.


  • -1
    D

    fan of 魔法少女小圆?


  • -1

    Yes, you too?


  • 0
    D

    yes, me too.


  • -1

    Glad to meet other 魔法少女小圆 fan on an online coding site. @madokamylove


  • 3
    H

    Hi, your last c++ code has undefined behavior when height is empty because r will be indexing invalid iterator. Also in C++ code with indexing, when using empty vector, you are doing (int)(0U - 1), whose result is implementation-dependent.


  • 0

    HI, I remember that you have used the same idea in another water problem. Really amazing solution.


  • 0

    Your code is fantastic! I'm too weak for this problem...


  • 2
    A

    @Hal you are not alone. I face a lot of problems as well while solving such problems. I guess practice will make us better.


  • 0

    It cost me 15 min to come up with a stupid stack solution. And another 45 min to write and debug. :(


  • 2
    S

    Here's the JAVA translation

    public int trap(int[] height) {
            if(height == null || height.length == 0) return 0;
            
            int n = height.length - 1;
            int level = 0, water = 0, index = 0;
            
            while(n > 0)
            {
                int lower = height[index] < height[index + n] ? height[index++] : height[index + n];
                
    			if(lower > level)
    				level = lower;
    			
    			water += level - lower;
    			
    			n--;
            }
            
            return water;
        }
    ```

  • 1

    Could someone please explain the logic being used in this question? Unfortunately, the single line comment by @StefanPochmann isn't enough to understand. Thank you.


  • -1
    S

    @暁美焔 NIUBI 大写的


  • 0
    M

    Amazing, Good job.


  • 0
    M

    amazing solution!


  • 1
    X

    @StefanPochmann
    One word: Sublime. Your code also reminds me of how stupid I am. I would probably never be able to come up with this kind of solution if I was locked in a room for 2 months with this problem.
    @BatCoder
    I have spent a lot of time understanding this solution. I would try to summarise my thoughts here:

    Consider this example: [3, X, 5], and we are working after the first iteration. That means l = 1 and r = 2

    What is the information that we need to figure out the amount of water that can be on X? We need only two things:

    • Maximum water that can be on X
    • Value of X

    Maximum water is not dependent on the value of X. It has to be obtained from the previous step. In this case, that has to be 3. Notice that the minimum of height[l] and height [r] of the previous step is also 3. This information is tracked by level. And X can only hold water if level is greater than X.

    There can be three cases of X.

    • X > level and X < 5: then X cannot hold any water, but we need to update level.
      For X = 4:
      lower = 4.
      level = max(4, 3) = 4
      water += (4 - 4) += 0

    • X < level, then X can hold water, and we don't have to update level since for the next step maximum water will still be level units.
      For X = 1:
      lower = 1,
      level = max(1, 3) = 3
      water += (3 -1) += 2

    • X > 5 > level: In this case lower will change to 5. And level also needs to change. since, if there were more bins between 5 and X, then from this steps point of view, maximum water permissible water will be 5 units.
      For X = 8:
      lower = 5
      level = max(5, 3) = 5
      water += (5 - 5) = 0

    Hope this helps.


  • 0
    B

    @暁美焔 said in 7 lines C / C++:

    Your code and idea are really fabulous to me. Thank you for your solution sharing.

    吼姆拉_(:з」∠)_


Log in to reply
 

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