all articles

leetcode war 11 - Container With Most Water

2017-09-19 @sunderls

leetCode js

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

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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.

brutal force

The brutal force solution cost us O(n2), with a nested loop.

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    var max = 0;
    var i = 0;
    var j = 0;
    var total = height.length;

    if (total < 2) {
        return 0;
    }

    for (;i <= total - 2; i++) {
        for (j = i + 1;j <= total - 1; j++) {
            max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
        }
    }

    return max;
};

well, of course, time limit Exceeded!

improvements

see if we can cut down some unnecessary comparison.

if ai is the largest container, what whould it be?

1. for i to 0
    if ai >= ai+1
        then ai+1 is not candidate, because ai has larger values both in x and y
    if ai < ai+1
        then we should calcuate the area
2. for i to n
    if ai >= ai-1
        then ai-1 is not candidate, same as above
    if ai < ai-1
        then we should calcuate the area

and then ........... I stuck here!!!

so, each pillar could be the left pillar or the right one right? according to above algorithm, we can safely flag the pillars, not for both, but for only one side?

so we do comparison and get two arrays of possible pillars.

  1. possible right pillars are a downward line
  2. possible left pillars are a upward line

does this improve ?

seems so, but I need to prove that later

how can we derive these two arrays?

like a toothed saw, we have to keep every tooth and compare like for possible right pillars

currentTooth = 0
couldBeRightPillar[]

for i from 0 to n
    couldBeRightPillar[i] = true
    k = i
    while a[k--] < a[i] && k >= currentTooth
            couldBeRightPillar[k] = false

# collect from couldBeRightPillar[]

do the reverse version to derive possible left pillars

improvement trial 1 - calculate possible borders first

var maxArea = function(height) {
    var total = height.length;

    if (total < 2) {
        return 0;
    }

    var couldBeRightPillars = [];
    var couldBeLeftPillars = [];
    var currentTooth = 0;

    var i = 0, k = 0;
    for (var i = 0; i < total; i++) {
        couldBeRightPillars[i] = true;
        k = i - 1;
        while (k >= currentTooth && height[i] >= height[k]) {
            couldBeRightPillars[k] = false;
            k -= 1;
        }
    }

    currentTooth = i = total - 1;
    k = 0;

    for (; i > -1; i--) {
        couldBeLeftPillars[i] = true;
        k = i + 1;
        while (k <= currentTooth && height[i] >= height[k]) {
            couldBeLeftPillars[k] = false;
            k += 1;
        }
    }

    // extrac possible pillars
    var possibleLeftPillars = [];
    var possibleRightPillars = [];

    for (i = 0; i < total; i++) {
        if (couldBeRightPillars[i]) {
            possibleRightPillars.push(i);
        }

        if (couldBeLeftPillars[i]) {
            possibleLeftPillars.push(i);
        }
    }

    var max = 0;
    // now calculate the result
    for (i = 0; i < total - 1; i++) {
        for (k = i + 1; k < total; k++) {
            max = Math.max(max, (k - i) * Math.min(height[i], height[k]));
        }
    }

    return max;
};

but still time exceeded

wait a minute, for a dot i to be a left pillar, with corresponding right pillar k

  1. a[i] < a[k]: then for j > k, a[j] must be smaller than a[k];
  2. a[i] > a[k]: then for j < i, a[i] must be smaller than a[i];

right pillars must be on the right, left pillars must be on the left, from these 2 assumptions, maybe we can caculate at same time, from both ends!!

improvement trial 2 - start from both ends

var maxArea = function(height) {
    var i = 0;
    var j = height.length - 1;
    var max = 0;

    while (i < j) {
        // if left one is smaller
        // then the container for left is at its max
        // we can safely skip i because this is most for it
        // * i and j + 1 may be larger by it is already check in j + 1 turn
        max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
        if (height[i] < height[j]) {
            i += 1;
        // same for the short right pillar
        } else if (height[i] > height[j]) {
            j -= 1;
        // if they are the same, then both are at there possible max
        } else {
            i += 1;
            j -= 1;
        }
    }

    return max;
};

accepted, ranking bottom 40% though

so I overthought the problem. the key here is that right pillar stays on the right and left to the left, which leads us to starting from both ends

about complexity: every number is compared only one time, so it should be O(n), right?

improvement trial 3 - skip slopes

thing is that when we can skip downward slopes on the left and upward slope on the right!


var maxArea = function(height) {
    var i = 0;
    var j = height.length - 1;
    var tmp = 0;
    var max = 0;

    while (i < j) {
        // if left one is smaller
        // then the container for left is at its max
        // we can safely skip i because this is most for it
        // * i and j + 1 may be larger by it is already check in j + 1 turn
        max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
        tmp = Math.min(height[i], height[j]);

        if (height[i] < height[j]) {
            i += 1;
            while (i < j && height[i] <= tmp) {
                i += 1;
            }
        // same for the short right pillar
        } else if (height[i] > height[j]) {
            j -= 1;
            while (j > i && height[j] <= tmp) {
                j -= 1;
            }
        // if they are the same, then both are at there possible max
        } else {
            i += 1;
            j -= 1;
        }
    }

    return max;
};

but only ranks up a little. what's there to be improved?!!

improvement trial 4 - avoid unnecessary if conditions

the problem seems to be that for height[i] === height[j], we can cut down this condition, merge it to height[i] <= height[j]

var maxArea = function(height) {
    var i = 0;
    var j = height.length - 1;
    var tmp = 0;
    var max = 0;

    while (i < j) {
        // if left one is smaller
        // then the container for left is at its max
        // we can safely skip i because this is most for it
        // * i and j + 1 may be larger by it is already check in j + 1 turn
        tmp = Math.min(height[i], height[j]);
        max = Math.max(max, (j - i) * tmp);

        if (height[i] <= height[j]) {
            i += 1;
            while (i < j && height[i] <= tmp) {
                i += 1;
            }
        // same for the short right pillar
        } else {
            j -= 1;
            while (j > i && height[j] <= tmp) {
                j -= 1;
            }
        } 
    }

    return max;
};

now it ranks top thirty, improved a lot.