Most frequently asked interview question #5 with solution

Given n non-negative integers a₁, a₂, ..., a_n , where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [4,8,4,5,6,4]. In this case, the max area of water (blue section) the container can contain is 48.

Solution in C++:

    int maxArea(vector<int>& height) {
       
            int max_area = 0;
            int it   = 0;
            int it_r = height.size() - 1;
            int curr_area =  0;
            int h1 = 0;
            int h2 = 0;
            int diff = 0;
        while( it != it_r ){
           
                h1   = height.at(it);
                h2   = height.at(it_r);
                diff = it_r - it;
            if(h1 > h2){
                curr_area = diff * h2;
                --it_r;
            }
            else{
                curr_area = diff * h1;
                ++it;
            }
           
            //Case: Current calculated area is greater than current max area
            if(curr_area > max_area){
                max_area = curr_area;
            }
           
        }
        return max_area;
    }