Nice explanation, concise and to the point. Just one note, this would fail for inputs of size 0 or nil. if (height == null || height.length == 0) return 0;
Two Pointer Approach static int CalculateWaterVolume(int[] arr) { int left = 0; int right = arr.Length - 1; int water = 0; int leftMax = 0; int rightMax = 0; while (left < right) { if (arr[left] < arr[right]) { //if arr left < left max that means we can trap water if (arr[left] < leftMax) { water += leftMax - arr[left]; } else // otherwise left max needs to be updated { leftMax = arr[left]; } left++; } else { if (arr[right] < rightMax) { water += rightMax - arr[right]; } else { rightMax = arr[right]; } right--; } } return water; } static void Main(string[] args) { int[] arr = new int[12] { 0, 1, 0, 2, 1 , 0 , 1 , 3, 2 , 1 , 2 , 1 }; Console.WriteLine("Water arr {0}", CalculateWaterVolume(arr)); Console.ReadKey(); }
hi thanks for the great video. I have a question on third for loop in dp solution. Shouldn't it be "for i in range(0, len(h))" instead of len(h) - 1? I am not understanding why we are leaving the last index out.
Hello, good question! so I think the last bar will never be able to store water because the water in the last bar will always slip over the edge to right. In the same sense we could have skipped the 0 index as the water would always slip over to the left. So I think it is even possibly to just loop from 1 to len(h) - 1. That being said I definitely did not see this while making the video and it was a mistake. But because of my reasoning I think the final answer will still be correct. Hope this helps!
Watched this and your histogram video, your explanations are really clear and concise, great job!
Thanks glad you found them helpful!
Nice explanation, concise and to the point. Just one note, this would fail for inputs of size 0 or nil.
if (height == null || height.length == 0) return 0;
Ah yes good catch thank you!
Thanks!
Awesome
Two Pointer Approach
static int CalculateWaterVolume(int[] arr)
{
int left = 0;
int right = arr.Length - 1;
int water = 0;
int leftMax = 0;
int rightMax = 0;
while (left < right)
{
if (arr[left] < arr[right])
{
//if arr left < left max that means we can trap water
if (arr[left] < leftMax)
{
water += leftMax - arr[left];
}
else // otherwise left max needs to be updated
{
leftMax = arr[left];
}
left++;
}
else
{
if (arr[right] < rightMax)
{
water += rightMax - arr[right];
}
else
{
rightMax = arr[right];
}
right--;
}
}
return water;
}
static void Main(string[] args)
{
int[] arr = new int[12] { 0, 1, 0, 2, 1 , 0 , 1 , 3, 2 , 1 , 2 , 1 };
Console.WriteLine("Water arr {0}", CalculateWaterVolume(arr));
Console.ReadKey();
}
hi thanks for the great video. I have a question on third for loop in dp solution. Shouldn't it be "for i in range(0, len(h))" instead of len(h) - 1? I am not understanding why we are leaving the last index out.
Hello, good question! so I think the last bar will never be able to store water because the water in the last bar will always slip over the edge to right. In the same sense we could have skipped the 0 index as the water would always slip over to the left. So I think it is even possibly to just loop from 1 to len(h) - 1. That being said I definitely did not see this while making the video and it was a mistake. But because of my reasoning I think the final answer will still be correct. Hope this helps!
@@KnapsackLabs thanks for the reply. yes that makes sense!