It has been a 8 months since my last post, as I was busy with school. Although school is still going on, I am going to try to keep doing Leetcode problems and these write ups. With that being said, today we will be going over the "Container With Most Water" problem from Leetcode. This problem had some interesting solutions, which we will be going over in this post. As always, source code is at the end of the post. Without further adieu, lets get right into it!
Container With Most Water
The given array gives us information of the position and heights of the given lines. Using this information, we need to find the maximum area of water the container can contain.
One thing to note is that the height used in the area calculation is the smallest height of the two lines (as shown in the example). Also, we are not told about a time requirement; though I did ran into some time issues when trying to submit my code the first time on Leetcode.
Solution
I first tried solving the problem using a brute force solution. What this solution does is that it tests every possible combination of width and height to find the maximum area. This is done by having an outer loop pick one line, and then have an inner loop go through the rest of the lines:
Since we are using two loops, we get a time complexity of O(N^2). When I submitted the brute force solution, I ended up exceeding the given time limit:
One reason would be the O(N^2) time complexity from the usage of two loops. The main issue would be that the loops would do the same calculations repeatedly (same lines and width). After thinking about the example for a bit, I realized that I can optimized by code by ignoring the lines behind the one I am testing:
The idea is that the lines behind "Line 1" was tested with Line 1 beforehand, meaning we do not have to conduct those calculations again. Following this procedure, by the time we get to the very last line in the array, we do not need to do any tests because every line before the last line was tested with the last line (it can be confusing to wrap one's head around).
This keeps the time complexity relatively close to O(N^2), but it is a faster solution.
Result
These are the results from my optimized brute force solution. I knew that the solution was going to be very slow, especially with the last test case being a large array of lines. I was looking at the official solutions to see how to achieve a faster run time, with one cleverly using double pointers and the fact that the height used in the area calculation is limited by the smallest line; giving a O(N) solution rather than my O(N^2).
Conclusion
Overall, this was yet another interesting problem to ponder about. Although my code has a long run time, it shows that sometimes a slow time complexity solution can still work if you optimized the right part of the code. I will be spending some time looking for a new problem and solving it as usual. Thank you for reading and I will see you then!
No comments:
Post a Comment