Trapping rain water algorithm complexity

Question

Trying to solve Trapping Rain Water problem, and can't understand why my solutions is not passing complexity check:

    public int Trap(int[] height) {
        int res = 0;
        int chk = 0;
        for(int i = 1; i < height.Length; i++){
            chk = Math.Min(height[..i].Max(),height[i..].Max())-height[i];
            if(chk > 0){
                res += chk;
            }
        }
        return res;
    }

Compile:    0.024s
Execute:    0.85s
Memory: 3.90Mb
CPU:    0.874s

But this one (recommended) is passing:

    public int Trap(int[] land) {
       var wall = 0;
        var water = new int[land.Length];
        for(var i = 0; i < water.Length; i++) {
            wall = Math.Max(wall, land[i]);
            water[i] = wall - land[i];
        }
        wall = 0;
        var sum = 0;
        for(var i = water.Length - 1; i >= 0; i--) {
            wall = Math.Max(wall, land[i]);
            water[i] = Math.Min(water[i], wall - land[i]);
            sum += water[i];
        }
        return sum;
    }

Compile:    0.024s
Execute:    0.03s
Memory: 0b
CPU:    0.054s

Why such a huge difference? Is it because of array slice[..i]?

Answer 1

Array Slicing operations are of O(N) time complexity.
So, the total time complexity of your code becomes O(N²).
That's the reason for the TLE.

While the recommended code is solving that problem within O(N) time complexity only.