You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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.
Output: 49
Explanation: 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.
The proof of why the solution works is important to understand. Following is its summary:
Consider we start with i = 0 and j = height.size() - 1. That is, i points to the first column and j points to the last column.
Now suppose that h(i)>h(j) (we are not loosing generality by this assumption)
We calculate the water capacity for the i, j. It will be h(j)*(j-i).
Now see that if we fix j at height.size() - 1 and vary i, we cannot get a greater water capacity. Why?
capacity = min of both heights * width between them. Since capacity is the product of these two terms, we will look at each term individually.
First about the width. It is easy to see that for all other i's (i = 1, 2,... ,height.size()-2) we will have a lesser width.
Second, the height will be the minimum of the column at i and at j, i.e. min(h(i),h(j)). But this value will be always less than h(j)
So both factors in the calculation of the capacity will be smaller and hence we can skip considering all the cases where i = 1, 2, 3, ..., height.size()-2 and j = height.size()-1
Which basically means that we can simply move j to j-1.
This is how I understood it and I hope this explanation makes it easy to understand.
Consider we start with i = 0 and j = height.size() - 1. That is, i points to the first column and j points to the last column.
Now suppose that h(i)>h(j) (we are not loosing generality by this assumption)
We calculate the water capacity for the i, j. It will be h(j)*(j-i).
Now see that if we fix j at height.size() - 1 and vary i, we cannot get a greater water capacity. Why?
capacity = min of both heights * width between them. Since capacity is the product of these two terms, we will look at each term individually.
First about the width. It is easy to see that for all other i's (i = 1, 2,... ,height.size()-2) we will have a lesser width.
Second, the height will be the minimum of the column at i and at j, i.e. min(h(i),h(j)). But this value will be always less than h(j)
So both factors in the calculation of the capacity will be smaller and hence we can skip considering all the cases where i = 1, 2, 3, ..., height.size()-2 and j = height.size()-1
Which basically means that we can simply move j to j-1.
This is how I understood it and I hope this explanation makes it easy to understand.
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Output: false
Explanation: "a" does not match the entire string "aa".
Java Hyd Team
Why this error ??
Try palindrome in this way your code execution will be fast
Common mistake
Some people will be tempted to come up with a quick solution, which is unfortunately flawed (however can be corrected easily):
Reverse SSS and become S′S'S
′
. Find the longest common substring between SSS and S′S'S
′
, which must also be the longest palindromic substring.
This seemed to work, let’s see some examples below.
For example, SSS = "caba", S′S'S
′
= "abac".
The longest common substring between SSS and S′S'S
′
is "aba", which is the answer.
Let’s try another example: SSS = "abacdfgdcaba", S′S'S
′
= "abacdgfdcaba".
The longest common substring between SSS and S′S'S
′
is "abacd". Clearly, this is not a valid palindrome.
Some people will be tempted to come up with a quick solution, which is unfortunately flawed (however can be corrected easily):
Reverse SSS and become S′S'S
′
. Find the longest common substring between SSS and S′S'S
′
, which must also be the longest palindromic substring.
This seemed to work, let’s see some examples below.
For example, SSS = "caba", S′S'S
′
= "abac".
The longest common substring between SSS and S′S'S
′
is "aba", which is the answer.
Let’s try another example: SSS = "abacdfgdcaba", S′S'S
′
= "abacdgfdcaba".
The longest common substring between SSS and S′S'S
′
is "abacd". Clearly, this is not a valid palindrome.