0

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?

Robert Ciocan
  • 11
  • 3
  • A list comprehension is only marginally faster than a for loop so it won't solve your speed issue. See [Are list-comprehensions and functional functions faster than "for loops"?](https://stackoverflow.com/questions/22108488/are-list-comprehensions-and-functional-functions-faster-than-for-loops) Your current algorithm has O(N**2) complexity. You need an algorithm with lower complexity. – DarrylG Sep 10 '22 at 08:03
  • Using list comprehension your solution is `maxim = max(min(height[i], height[j]) * abs(j - i) for i in range(0, len(height)) for j in range(0, len(height)))` (using generator). But, this is still O(N**2). For an O(N) solution see [Container with Most Water](https://www.geeksforgeeks.org/container-with-most-water/) – DarrylG Sep 10 '22 at 08:24

1 Answers1

1

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.

AdilW
  • 24
  • 1
  • 3
  • Oh yea, I didn't see my mistake there . But you are right , it doesn't change my complexity so the solution isn't accepted( it's on leetcode so mabye you know it from there) – Robert Ciocan Sep 10 '22 at 08:13