I want to solve this problem, but this isn't my issue. I only give this as context.

"You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store." The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

I made a simple nested for loop to solve this problem:

    for i in range(0, len(height)):
        for j in range(0, len(height)):
            maxim = max(min(height[i], height[j]) * abs(j - i),maxim)

But this solution takes too long for a bigger array. So I tried to do this with List Comprehension:

mxm = [min(height[i], height[j] * abs(j - i)) for i in range(0, len(height)) for j in range(0, len(height))]
    maxim = max(mxm)

The problem is , I have 2 different outputs: the nested for loop works (it returns 49) but the second one returns 8. (the mxm array has these elements: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 6, 4, 8, 8, 8, 8, 8, 2, 6, 0, 2, 6, 6, 6, 6, 6, 2, 2, 2, 0, 2, 2, 2, 2, 2, 4, 5, 5, 2, 0, 4, 5, 5, 5, 4, 4, 4, 4, 4, 0, 4, 4, 4, 6, 8, 8, 6, 8, 4, 0, 3, 8, 3, 3, 3, 3, 3, 3, 3, 0, 3, 7, 7, 7, 7, 7, 7, 7, 3, 0])

Why are they different? And how can I make my solution faster?

CodePudding user response：

In the first example you're applying the min function to just the height values

min(height[i], height[j])

In the second you include the absolute distance between index positions in that min function as well, it'll always apply to height[j] instead of the actual minimum.

min(height[i], height[j] * abs(j - i))

Also regarding your solution, I believe ive seen this problem before. I think what you're looking for is a sliding window.