{"id":4299,"date":"2023-08-11T17:17:10","date_gmt":"2023-08-11T11:47:10","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4299"},"modified":"2023-08-11T17:17:11","modified_gmt":"2023-08-11T11:47:11","slug":"container-with-most-water","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/container-with-most-water\/","title":{"rendered":"Container With Most Water"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-1-brute-force\">Approach 1: Brute Force<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#approach-2-two-pointers\">Approach 2: Two Pointers<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code-implementation\">Python Code Implementation<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-how-is-the-area-between-the-two-points-found\">Q.1: How is the area between the two points found?<\/a><\/li><li><a href=\"#q2-what-is-the-most-efficient-approach-to-solving-this-problem\">Q.2: What is the most efficient approach to solving this problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given n non-negative integers a1, a2, &#8230;, an, where each represents a point at coordinate (i, ai). &#8216;n&#8217; vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).<br>Find two lines, which together with the x-axis form a container, such that the container contains the most water.<\/p>\n\n\n\n<p>Your program should return an integer that corresponds to the maximum area of water that can be contained ( Yes, we know maximum area instead of maximum volume sounds weird.<br>But this is a 2D plane we are working with for simplicity ).<\/p>\n\n\n\n<p>Note: You may not slant the container.<\/p>\n\n\n\n<ul><li><strong>Examples:Input:\u00a0 <\/strong>height[] = {1,8,6,2,5,4,8,3,7}<strong>\u00a0<\/strong><\/li><li><strong>Output:<\/strong> 49<\/li><li><strong>Explanation: <\/strong>The maximum area is the area denoted by the blue section. The total area is 49 units.<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"640\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4465 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image--1024x640.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image--1024x640.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image--300x188.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image--768x480.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image--1536x960.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image--380x238.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image--550x344.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image--800x500.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image--1160x725.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/image-.png 1600w\" ><\/figure>\n\n\n\n<ul><li><strong>Input:\u00a0 <\/strong>height[] = {1, 1}<strong>\u00a0<\/strong><\/li><li><strong>Output:<\/strong> 1<\/li><\/ul>\n\n\n\n<h2 id=\"approach-1-brute-force\">Approach 1: Brute Force<\/h2>\n\n\n\n<p>The most basic approach to solve this problem is to simplify all possible areas for every pair of line segments and maximize it.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Initialise <strong>maxarea = 0<\/strong>.<\/li><li>Run a nested loop i = 0 till i = N and j = i + 1 till N.<ul><li>The area would be the <strong>min(height[i], height[j]) * (j &#8211; i)<\/strong><\/li><li>Maximize the area for every iteration.<\/li><\/ul><\/li><li>Return <strong>maxarea.<\/strong><\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\"><span id=\"c-code-implementation-2\">C++ Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int maxArea(vector&amp;lt;int> height) {\n    int maxarea = 0;\n    for (int i = 0; i &amp;lt; height.size(); i++)\n      for (int j = i + 1; j &amp;lt; height.size(); j++)\n        maxarea = max(maxarea, min(height[i], height[j]) * (j - i));\n    return maxarea;\n }<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\"><span id=\"java-code-implementation-2\">Java Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public class Solution {\n  public int maxArea(int[] height) {\n    int maxarea = 0;\n    for (int i = 0; i &amp;lt; height.length; i++)\n      for (int j = i + 1; j &amp;lt; height.length; j++)\n        maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));\n    return maxarea;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\"><span id=\"python-code-implementation-2\">Python Code Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def maxArea(heights):\n    maxarea = 0\n    for i in range(len(heights)):\n        for j in range(i + 1, len(heights)):\n            maxarea = max(min(heights[i], heights[j]) * (j - i)\n    return maxarea<\/pre>\n\n\n\n<ul><li><strong>Time Complexity: <\/strong>O(N^2), where N is the size of the array<\/li><li><strong>Space Complexity:<\/strong> O(1) since no extra space is used.<\/li><\/ul>\n\n\n\n<h2 id=\"approach-2-two-pointers\">Approach 2: Two Pointers<\/h2>\n\n\n\n<p>The most basic observation is that the area formed between the lines will always be limited by the height of the minimum. So, the larger the distance, the greater the area.<br>Check the below illustration to solve the problem:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1457\"  height=\"1204\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4466 pk-lazyload\"  data-pk-sizes=\"auto\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/GIF-06.gif\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Take two pointers, one at <strong>i = 0<\/strong> and another pointer <strong>j = N &#8211; 1<\/strong>.<\/li><li>Consider a variable maxarea = 0, for calculating maxarea till index i.<\/li><li>At every step, calculate the maxarea between them the two lines pointed i.e. height[i] and height[j] and update maxarea.<\/li><li>Keep incrementing the pointer pointed at a smaller height towards each other.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-implementation\">C++ Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int maxArea(vector&amp;lt;int> height) {\n    int maxarea = 0, l = 0, r = height.size() - 1;\n    while (l &amp;lt; r) {\n      maxarea = max(maxarea, min(height[l], height[r]) * (r - l));\n      if (height[l] &amp;lt; height[r])\n        l++;\n      else\n        r--;\n    }\n    return maxarea;\n  }<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\">Java Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public class Solution {\n  public int maxArea(int[] height) {\n    int maxarea = 0, l = 0, r = height.length - 1;\n    while (l &amp;lt; r) {\n      maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));\n      if (height[l] &amp;lt; height[r])\n        l++;\n      else\n        r--;\n    }\n    return maxarea;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code-implementation\">Python Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def maxArea(height):\n    L, R, width, res = 0, len(height) - 1, len(height) - 1, 0\n    for w in range(width, 0, -1):\n        if height[L] &amp;lt; height[R]:\n            res, L = max(res, height[L] * w), L + 1\n        else:\n            res, R = max(res, height[R] * w), R - 1\n    return res<\/pre>\n\n\n\n<ul><li><strong>Time Complexity: <\/strong>O(N),\u00a0 where N is the size of the array<\/li><li><strong>Space Complexity:<\/strong> O(1) since no extra space is used.<\/li><\/ul>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/container-with-most-water\/\" target=\"_blank\">Container With Most Water<\/a><\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-how-is-the-area-between-the-two-points-found\"><span id=\"q-1-how-is-the-area-between-the-two-points-found\">Q.1: How is the area between the two points found?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>Since the width of each consecutive block is considered to be 1, the length is simply the distance between the two points and the height is the minimum between the two heights.<\/p>\n\n\n\n<h3 id=\"q2-what-is-the-most-efficient-approach-to-solving-this-problem\"><span id=\"q-2-what-is-the-most-efficient-approach-to-solving-this-problem\">Q.2: What is the most efficient approach to solving this problem?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> The two-pointer method is the most efficient way to solve this problem. The time complexity is O(N) and the space complexity is O(1).<strong><br><\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given n non-negative integers a1, a2, &#8230;, an, where each represents a point at coordinate (i,&hellip;\n","protected":false},"author":5,"featured_media":4467,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[457,613],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4299"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4299"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4299\/revisions"}],"predecessor-version":[{"id":22673,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4299\/revisions\/22673"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4467"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4299"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4299"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4299"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}