LeetCode Problem #11 Container With Most Water

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.

The 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.

Problem Link

Solution Number One O(n^2) Brute Force :

Try all valid combinations
outer loop start from i = 0 to length of array
inner loop start from j = i+1 to length of array
compare current area with new area and choose max.
return max area.

Solution Number Two O(n) :

Linear Solution greedy algorithm:

calculating area it is rectangle

width = rightIndex - leftIndex
height = min (height[rightIndex], height[leftIndex])

select max area
update leftIndex and rightIndex

if height[rightIndex] > height[leftIndex] this means we should search for another left leftIndex++
else we need to search for another right rightIndex--

return max area

Thank you,
AhmedG.

Comments

DevExpress C# Chart Tutorial

Hello , this blog post about Charting in DevExpress , I faced many problems I visited hundreds of pages to solve this problems , actually it was the first time I use DevExpress Charts, Work is not like school or university , in school if you don't know thing you can learn it any time you want , in work you have to do today task yesterday, I like to share my knowledge and skills with you , I hope this Post help you . // clear series on chart chart.Series.Clear(); // clear Titles of chart chart.Titles.Clear(); // legend alignment chart.Legend.AlignmentHorizontal = LegendAlignmentHorizontal.Center; chart.Legend.AlignmentVertical = LegendAlignmentVertical.Bottom; chart.Legend.Direction = LegendDirection.LeftToRight; // creating series // series view Type example Line DevExpress.XtraCharts.Series series = new DevExpress.XtraCharts.Series("series name ", ViewType.Line); // add title DevExpress.XtraCharts.ChartTitle chtTitle = new DevExpress.XtraCharts.Cha...

Recursion

Recursion is a programming technique which function calls itself , this seems strange , however it is one of the most interested and effective technique in programming. it helps you write code in less statements and provides unique conceptual frame work to solve problems. lets discus some problems to know how it works : first example Triangular Numbers : it is series like : 1,3,6,10,15,21........ etc our program should get the nth term in the series, the numbers in this series called triangular numbers due to they can be visualized as a triangle. triangular numbers fig 1 finding the nth term using a loop see this figure : loop adding 1+2+3+4 and so on code is easy , a loop will add numbers from n to 0 like this int triangle(int n) { int total = 0; while(n > 0) // until n is 1 { total = total + n; // add n (column height) to total --n; // decrement column height } return total; } it easy enough and for sure it is fast . before we start the recu...

LeetCode Problem #19 Remove Nth Node From End of List

Solution for LeetCode Problem #19 Remove Nth Node From End of List it is linked list problem can be solved with multiple solutions, but I'm gonna solve it with fastest solution in java. Problem link we should assign dummy_head it is common while solving linked list problems Assign 2 iterators slow and fast both equals to dummy_head we don't know the length of the list but we know it is always valid, so we will move with a window of size n+1 when we reach the end by the fast iterator the slow iterator will be in the node n+1 from the last , right? we will assign slow.next to be equal slow.next.next we are dropping the node n from last, got it? we will return dummy_head.next Thank you, AhmedG

Ahmed Ghazey

Search This Blog