C Program/Trapping_Rain_Water.c
// Function to find amount of water that can be trapped within
// given set of bars in linear time and constant space
Function to find amount of water that can be trapped within
given set of bars in linear time and constant space
Function to find amount of water that can be trapped within given set of bars in linear time and constant space
int trap(int heights[], int n)
{
	int left = 0, right = n-1, water = 0;
	int maxLeft = heights[left];
	int maxRight = heights[right];
	while (left < right)
	{
		if (heights[left] <= heights[right])
		{
			left++;
			maxLeft = max(maxLeft, heights[left]);
			water += (maxLeft - heights[left]);
		}
		else
		{
			right--;
			maxRight = max(maxRight, heights[right]);
			water += (maxRight - heights[right]);
		}
	}
	return water;
}
int trap ( int heights [ ] , int n ) { int left = 0 , right = n - 1 , water = 0 ; int maxLeft = heights [ left ] ; int maxRight = heights [ right ] ; while ( left < right ) { if ( heights [ left ] <= heights [ right ] ) { left ++ ; maxLeft = max ( maxLeft , heights [ left ] ) ; water += ( maxLeft - heights [ left ] ) ; } else { right -- ; maxRight = max ( maxRight , heights [ right ] ) ; water += ( maxRight - heights [ right ] ) ; } } return water ; }
Function to find amount of water that can be trapped within
given set of bars in linear time and constant space
Function to find amount of water that can be trapped within given set of bars in linear time and constant space
// maintain two pointers left and right pointing to leftmost and // rightmost index of the input array