Volume of water that can be filled in the valley

Given a one dimensional array of integers representing the valley configuration, determine the total volume of water that can be filled without any spillover.
Elevation

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        public static void Main(string[] args)
        {
            int[] elevationArray = { 1, 2, 3, 1, 2, 1, 4, 6, 5, 4, 2, 3, 4, 1 };
            int waterVolume = 0, flag = 0;
            while (flag == 0)
            {
                flag = 1;
                int start = -1, end = -1;
                for (int i = 0; i < elevationArray.Length - 1; i++)
                {
                    if (elevationArray[i] > elevationArray[i + 1]) //dip
                    {
                        start = i;
                    }
                    else if (elevationArray[i] < elevationArray[i + 1] && start != -1) //rise followed by a dip
                    {
                        end = i + 1;
                        Console.WriteLine("Start = " + start + " End = " + end);
                        for (int j = start + 1; j < end; j++)
                        {
                            waterVolume = waterVolume + (Math.Min(elevationArray[start], elevationArray[end]) - elevationArray[j]);
                            elevationArray[j] = Math.Min(elevationArray[start], elevationArray[end]);
                        }
                        flag = 0; //need to iterate again
                        start = -1; //reset start position
                    }
                }
            }
            Console.WriteLine("Water Volume = " + waterVolume);
        }
    }
}

Output
=======
Start = 2 End = 4
Start = 4 End = 6
Start = 9 End = 11
Start = 2 End = 6
Start = 9 End = 12
Water Volume = 8
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s