Here is a fun problem dealing with arrays.
Given n non-negative integers a1, a2, ..., a(n), 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 an 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
Looking at this problem there are two ways I would attack it. The first being a brute force approach and iterating through possible combinations of walls to find the boundary that holds the most water.
Brute Force Approach 👊
Looking at a double for loop approach, the most important factor for this problem is the smallest wall. Iterating with two indices you can pick the smallest wall and multiply that wall by the distance between the two indices.
Two pointer approach:
Looking to see how we can improve upon this process we can two different pointers to yield us a better BigO notation of O(n).
Hope you liked this post, please follow and clap for more! Throw your implementations in the comments below! 🙏
Top comments (0)