Hello, Welcome to my Day 2 of #30Days of Problem Solving and finding solutions to Leetcode's Data Structures and Algorithm questions. Here, I choose a question daily and try to solve it, and finally pen down my process of flow in solving the question.

I hope you find it helpful. Today I will be solving Leetcode's question 11 - Container With Most Water

Problem Statement

• You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i<sup>th</sup> 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.

Example 1
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.

Example 2
Input: height = [1,1]
Output: 1

Thought Process/ Intuition

One approach I had to solve this question was to use a brute force approach. We can calculate the area of all possible containers formed by every pair of lines and keep track of the maximum area found. This would involve using nested loops to compare every pair of lines and then computing the area of the container formed by those lines. The maximum area found so far can be updated if the area of the current container is greater than the previous maximum.

While this approach will work, it has a time complexity of O(n^2), where n is the length of the input array. This is because we are comparing every pair of lines, so the number of comparisons we make is proportional to n^2. Therefore, for large input sizes, this approach would be too slow.

Here is the code for the brute force approach

class Solution:
    def maxArea(self, height: List[int]) -> int:
        res = 0
        for l in range(len(height)):
            for r in range(l + 1, len(height)):
                area = (r -l) *min(height[l], height[r])
                res = max(res, area)

In the given implementation, the two nested loops are used to iterate over all possible pairs of lines. For each pair, the area of the container formed by that pair is calculated using the formula area = (r -l) *min(height[l], height[r]), where l and r are the indices of the two lines being considered, and height[l] and height[r] are the heights of those lines.

The maximum area found among all pairs is updated in the variable res using the max function. After all, pairs have been considered, the final value of res is returned as the maximum amount of water that a container can store.

The Approach

A more efficient approach to solve this problem is to use the two-pointer approach, which can solve the problem in O(n) time. In this approach, we use two pointers, one starting from the left end of the array, and the other starting from the right end. We then move the pointer corresponding to the shorter line towards the center of the array, and compute the area of the container formed by those lines. We keep track of the maximum area found so far, and repeat this process until the two pointers meet in the center. This approach is more efficient because we only need to compare every pair of lines once, resulting in a time complexity of O(n).

class Solution:
    def maxArea(self, height: List[int]) -> int:
        res = 0
        l, r = 0, len(height) - 1 

        while l < r:
            area = (r -l) * min(height[l], height[r])
            res = max(res, area)

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return res

This implementation uses the two-pointer approach that I described earlier to solve the problem. The two-pointers, l and r, are initialized to point to the left and right ends of the array, respectively.

The while loop runs until l and r meet, which happens when l >= r. In each iteration of the loop, the area of the container formed by the lines at l and r is calculated using the formula area = (r -l) *min(height[l], height[r]). If the current area is greater than the previous maximum area, res, then res is updated to the current area.

Then, the pointer corresponding to the shorter line is moved toward the center of the array. If height[l] < height[r], then l is incremented by 1, otherwise r is decremented by 1. This step is crucial to the efficiency of the algorithm, because it ensures that we are always moving the pointer corresponding to the shorter line. This guarantees that we will eventually find the maximum amount of water that a container can store.

After the pointers meet, the final value of res is returned as the maximum amount of water that a container can store.

Complexity

Time Complexity:

0(n)
The time complexity of this approach is O(n), where n is the length of the input array. This is because we traverse the array once, and for each step, we either move the left pointer one step towards the center of the array or move the right pointer one step towards the center of the array. Therefore, each pointer can move at most n-1 steps, resulting in a total of O(n) steps.
Since the time complexity of the two-pointer approach is O(n), it is more efficient than the brute force approach, which has a time complexity of O(n^2).

Space Complexity:

0(1)
there are no extra data structures used in the code, other than the input array and a few variables used for bookkeeping. Since the space used by these variables is constant, the space complexity of this code is O(1), which means that the space required by the algorithm is constant and does not depend on the size of the input array

Conclusion

To conclude, the problem asks us to find two lines in an array of heights that, when used as the walls of a container, can hold the maximum amount of water. We can solve this problem using the two-pointer approach, which involves using two pointers, one starting from the left end of the array, and the other starting from the right end. We then move the pointer corresponding to the shorter line toward the center of the array and compute the area of the container formed by those lines. We keep track of the maximum area found so far and repeat this process until the two pointers meet in the center. This approach has a time complexity of O(n) and a space complexity of O(1).

By using this approach, we can efficiently find the maximum amount of water that a container can hold with a single pass over the input array, making it a very efficient solution to the problem.