online advertising

Sunday, July 12, 2015

LeetCode OJ - Container With Most Water

Problem:

Please find the problem here.

Solution:

The problem description sucks - it is NOT about the size of the container when the lines are all there. It is about picking two lines from the set of lines to create a biggest container.

In more abstract terms, it is about finding $ l $ and $ r $ such that $ \min(h[l], h[r]) \times (r - l ) $ is maximized.

It is trivial to write a quadratic algorithm - but the judge do not accept it - it must be faster.

Divide and conquer? It seems that the subproblems does not help (in terms of complexity) improving the performance of solving the merge problem.

Dynamic programming? I found hard to solve the 'extend the problem size by 1' problem.

Finally, a friend of mine hinted on trying to reduce the l, r range. Then I basically get it. The key idea is simple.

In order to optimize a product, if you decrease one operand, you have to increase its another operand.

What a trivial principle, right? Now we will apply it to the product we are trying to optimize. The right hand side operand is maximized when l = 0 and r = height.size() - 1. Now we reduce the range, so the another operand must be increased, right? So we increase it by moving the l or r or both pointers! We do NOT stop the search until the left hand side increases.

Since we consider each number only once and then we will move forward, the algorithm is linear. If the description above is not clear, here is the code:

Code:

#include "stdafx.h"

// https://leetcode.com/problems/container-with-most-water/

#include "LEET_CONTAINER_WITH_MOST_WATER.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_CONTAINER_WITH_MOST_WATER
{
    class Solution
    {
    public:
        int maxArea(vector<int>& height)
        {
            if (height.size() < 2)
            {
                // There is no container!
                return - 1;
            }

            unsigned int l = 0; 
            unsigned int r = height.size() - 1;
            int currentHeight = min(height[r], height[l]);
            int bestAreaSoFar = currentHeight * ( r - l );
            while (l < r)
            {
                unsigned int lSearch = l;
                unsigned int rSearch = r;
                while (lSearch < height.size() && height[lSearch] <= currentHeight)
                {
                    lSearch++;
                }
                while (rSearch > 0 && height[rSearch] <= currentHeight)
                {
                    rSearch--;
                }
                if (lSearch < rSearch)
                {
                    l = lSearch;
                    r = rSearch;
                    currentHeight = min(height[r], height[l]);
                    int areaSoFar = currentHeight * ( r - l );
                    if (areaSoFar > bestAreaSoFar)
                    {
                        bestAreaSoFar = areaSoFar;
                    }
                }
                else
                {
                    break;
                }
            }
            
            return bestAreaSoFar;
        }
    };
};

using namespace _LEET_CONTAINER_WITH_MOST_WATER;

int LEET_CONTAINER_WITH_MOST_WATER()
{
    Solution solution;
    int case1[] = { 1, 2, 3, 4, 5, 6 };
    int case2[] = { 6, 5, 4, 3, 2, 1 };
    int case3[] = { 4, 3, 2, 4 };
    int case4[] = { 4, 3, 2, 5 };
    int case5[] = { 4, 3, 2, 4, 4, 3, 2, 5 };
    int case6[] = { 4, 3, 2, 5, 4, 3, 2, 4 };
    int case7[] = { 1, 2, 1 };
    cout << (solution.maxArea(vector<int>(case1, case1 + _countof(case1))) == 9) << endl;
    cout << (solution.maxArea(vector<int>(case2, case2 + _countof(case2))) == 9) << endl;
    cout << (solution.maxArea(vector<int>(case3, case3 + _countof(case3))) == 12) << endl;
    cout << (solution.maxArea(vector<int>(case4, case4 + _countof(case4))) == 12) << endl;
    cout << (solution.maxArea(vector<int>(case5, case5 + _countof(case5))) == 28) << endl;
    cout << (solution.maxArea(vector<int>(case6, case6 + _countof(case6))) == 28) << endl;
    cout << (solution.maxArea(vector<int>(case7, case7 + _countof(case7))) == 2) << endl;
    return 0;
}

No comments :

Post a Comment