Container with Most Water and Longest Common Prefix

Problem Statement:

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

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

Solution One: Brute force

Iterate each pair columns and calculate the water capacity. Find the maximum of them. The idea is so simple and straightforward, I will give the code directly.

Time Complexity: O(n^2)

Space Complexity: O(1)

Solution Two:

Let’s take a close look at the problem. Since what we are really interested is the max capacity of water, while the capacity of the water is defined by both the width between the two columns and the height of the shorter column. So we can start from the first column and the last column, which means at first iteration, we have the max width, so in order to calculate the max water capacity, we need to trade width for height, which means we need to traverse the column from both ends to the other end. We stop the traverse until both of the pointers meet with each other. How should we move the column?

We compare both the current column, find the shorter one, and traverse from that one to another one. We keep this progress until we have touched all the columns. We can easily prove this progress will work, basically ,when we traverse the columns, we will have several situations:

1. If there is only one or no column(s) taller than the first two column, we can safely say that the first two columns forms the max water capacity container;

2. If there are two or more columns taller than the first two column, we can guarantee that we will final touch them, and calculate the area.

What if we encounter the situation that current columns have the same height? We pick up either one and traverse from that forward. Note no matter how you traverse, the final answer is determined, because the taller columns we will definitely touch, the shorter column will never provide larger water capacity.

Time Complexity: O(n)

Space Complexity: O(1)

Problem Statement:

Input: ["flower","flow","flight"]
Output: "fl"

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Solution One: Vertical Comparison

The idea is simple, we compare from the first element of each sub string. Then we iterate over the sub string. We return either the shortest sub string reaches its end or we find an element which is not the common prefix in both sub strings. Look at the picture below:

Time Complexity: O(n*m) n is the number of sub string in strs, m is the shortest sub string length.

Space Complexity: O(1) We do not need any temporal arrays or strings.

Solution Two: Horizontal Comparison

A similar idea to vertical comparison, this time, instead of comparing the element in each sub string one by one, we first compare sub string 0 and 1, we get a temporal result, then we use this result to compare with the third one, and update the result. After that, we compare with the fourth one, so on and so forth. Look at the picture below:

The code is not complex as well.

Time Complexity: The worst case, if all the sub strings have length m, and they are the same, we need O(n*m)

Space Complexity: O(1)

Solution Three: Recursion

We can look at this problem in this way: since strs is a string list which contains a huge number of sub strings. If we want to know the common prefix of all the sub strings, we can divide the sub string into two parts, and calculate the common prefix of left part and right part respectively. If we want to know the left prefix, we can keep dividing the left part into two parts… so finally, we will get the common prefix of only one sub string, the common prefix of that string is itself. So we can return that. Look at the picture below:

The code is  a little bit complex.

Time complexity: O(n * m), For recursive part, the time complexity is 2*n – 1, draw a recursive tree, and calculate the node we will generate.  m is the average sub string comparisons cost, we use this to generate the common prefix.

Space Complexity: O(n), n is the number of recursive call.

Solution Four: Sorting and Comparison

Since we need to find the longest common prefix of all sub strings, and we know that common prefix is the same to all sub strings. So we can sort the whole strs in alphabetical order by utilizing the C++ sort() method. After that, we only need to compare the first one (shortest one) and the last one.

Time Complexity: O(MAX(n*lgn, m)), m is the length of the shortest sub string, n is the number of sub strings. When we do sorting, we need at least n*lgn cost.

Space Complexity: O(m). You can remember the index and return sub string of strs[0].substr(0, i), which will give you O(1). For me, it’s OK.

That’s all for today, thanks for reading.