LeetCode: Container With Most Water

Initial version:
O(n*n)
compare area of all two points.
too time consuming and cannot pass test.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: int maxArea(vector<int>& height) { int area=0; for(int i = 0; i < height.size(); i++){ for(int j = i + 1; j < height.size(); j++){ int w = j - i; int h = (height[i] < height[j]) ? height[i] : height[j]; int temparea = w * h; if(temparea > area) area = temparea; } } return area; } };

Analysis:
This version can be optimized by recording the min height which has been iterated. If the current height is less than the recorded min height, all areas that stared with current height will less than the max area started with the recorded min height. So we don't need to calculate areas started with current height and just jump to the next element.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: int maxArea(vector<int>& height) { int area=0; int minh=height[0]; for(int i = 0; i < height.size(); i++){ if(height[i] < minh) continue; for(int j = i + 1; j < height.size(); j++){ int w = j - i; int h = (height[i] < height[j]) ? height[i] : height[j]; int temparea = w * h; if(temparea > area) area = temparea; } } return area; } };

However, the time complexity is still O(n*n) in worst case.

Two-pointer scan:
O(n)
Area is only decided by the beginning and ending heights.
When the short side is fixed, the area reduces when the right side moves forward the short side. So we can keep the tall side and only move the short side. This makes sure that the largest area will be iterated.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

class Solution { public: int maxArea(vector<int>& height) { int left = 0; int right = height.size() - 1; int maxArea = 0; while(left < right){ int w = right - left; int h = (height[left] < height[right]) ? height[left] : height[right]; int area = w * h; if(area > maxArea) maxArea = area; if(height[left] < height[right]) left++; else right--; } return maxArea; } };

Reference:
http://yucoding.blogspot.com/2012/12/leetcode-question-22-container-with.html