- Denisse's Newsletter
- Posts
- Day 8
Day 8
Denisse Damian
February 13, 2024
Hello and welcome back brave human being,
Given an array of integers, each index represents a line in a 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. |
Before we delve into the solution, let’s think about the naive solution.
We can calculate all of the possible areas in a double for loop and look for the Maximum Area.
To calculate the base we do the difference between both lines in the y-axis.
To calculate the height we take the smallest height of the two lines.
This approach would result in an )O(n2).
Could we solve it with two-pointers? Yes, my friend.
We can solve it with two-pointers and no sorting. Sorting would be out of the question since the index of the lines can’t be moved.
We would have to initialize two-pointers and a global maximum area.
L=0
R=Array.size()-1
MaxArea=-1
Then at each step of the algorithm, we calculate the area and compare it to MaxArea, if it is greater, we update it.
To decide how to move our pointers, we are going to anchor the tallest line and move our pointer who has the lower height. If both lines are the same, we move both.
Let’s dig in with an example:
What would the time complexity be? |
Need motivation to be consistent?
Add this problem to your log and when the challenge is done send it to me! You’ll be in for a treat.
Reply