11. Container With Most Water.ipynb

{
  "cells": [
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# 11. Container With Most Water\n\nhttps://leetcode.com/problems/container-with-most-water/description/"
    },
    {
      "metadata": {
        "collapsed": true
      },
      "cell_type": "markdown",
      "source": "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.\n\n__Note:__ You may not slant the container and n is at least 2.\n\n![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/17/question_11.jpg \"Problem visualization\")\n\nThe 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.\n\n__Example__\n\n`Input: [1,8,6,2,5,4,8,3,7]\nOutput: 49`"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "from itertools import combinations",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def volume(h1, h2):\n    distance = abs(list(h1.keys())[0] - list(h2.keys())[0])\n    height = min(list(h1.values())[0], list(h2.values())[0])\n    return distance * height",
      "execution_count": 29,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "class Solution:\n    def maxArea(self, height):\n        \"\"\"\n        :type height: List[int]\n        :rtype: int\n        \"\"\"\n        from itertools import combinations\n        dict_data = [{index: value} for index, value in enumerate(height)]\n        comb = list(combinations(dict_data, 2))\n        volume = lambda h1, h2: abs(list(h1.keys())[0] - list(h2.keys())[0]) * min(list(h1.values())[0], list(h2.values())[0])\n        return max([volume(c[0], c[1]) for c in comb])",
      "execution_count": 47,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "sol = Solution()\ndata = [1,8,6,2,5,4,8,3,7]\nsol.maxArea(data)",
      "execution_count": 48,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 48,
          "data": {
            "text/plain": "49"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "",
      "execution_count": null,
      "outputs": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python36",
      "display_name": "Python 3.6",
      "language": "python"
    },
    "language_info": {
      "mimetype": "text/x-python",
      "nbconvert_exporter": "python",
      "name": "python",
      "pygments_lexer": "ipython3",
      "version": "3.6.6",
      "file_extension": ".py",
      "codemirror_mode": {
        "version": 3,
        "name": "ipython"
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}