Trapping Rain Water
Given an M * N matrix, where the value at any cell denotes the height of that cell in a 2-D elevation map. You need to find the volume of water that can be trapped within it.

For a matrix = [ 5, 5, 5 ] [ 5, 2, 3 ] [ 6, 9, 8 ] 2-D elevation map will look like this

After the rain, a total of 1 unit volume of water gets trapped, and this 2-D elevation map will look like this

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases. The first line of each test case contains two space-separated integers ‘M’ and ‘N’ denoting the number of rows and columns in the matrix. The next ‘M’ lines contain ‘N’ space-separated integers denoting the height of each cell.

Output Format:

For each test case, print a single integer denoting the volume of water that can be trapped. Print the output of each test case in a separated line.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Trapping Rain Water

Given an M * N matrix, where the value at any cell denotes the height of that cell in a 2-D elevation map. You need to find the volume of water that can be trapped within it.

For a matrix = 
[ 5, 5, 5 ]
[ 5, 2, 3 ]
[ 6, 9, 8 ]  

2-D elevation map will look like this

After the rain, a total of 1 unit volume of water gets trapped, and this 2-D elevation map will look like this

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘M’ and ‘N’ denoting the number of rows and columns in the matrix.

The next ‘M’ lines contain ‘N’ space-separated integers denoting the height of each cell.

Output Format:

For each test case, print a single integer denoting the volume of water that can be trapped.

Print the output of each test case in a separated line.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= M,N <= 100
1 <= matrix[i][j] <= 10^3

Where ‘T’ is the number of test cases, ‘M’ and ‘N’ are the dimensions of the given matrix.
Matrix[i][j] is the height of the cell at the ‘i-th’ row and ‘j-th’ column.

Time Limit: 1 sec.

Accepted Answer

1. Create two array left and right of size n. create a variable max_ = INT_MIN.
2. Run one loop from start to end. In each iteration update max_ as max_ = max(max_, arr[i]) and also assign left[i] = max_
3. Update max_ = INT_MIN.
4. Run another loop from end to start. In each iteration update max_ as max_ = max(max_, arr[i]) and also assign right[i] = max_
5.Traverse the array from start to end.
6. The amount of water that will be stored in this column is min(a,b) – array[i],(where a = left[i] and b = right[i]) add this value to total amount of water stored
7. Return the total amount of water stored.

Accepted Answer

Priority Queue Implementation.

Approach: The border cells can never hold water as water will always flow out from there. So we will assume all the border cells as our boundary.

Now the water that can behold at least inside the cells will be equal to the minimum height of the boundary.

For eg if matrix = [ 8, 8, 8, 8 ]

[ 6, x, x, 8 ]

[ 6, x, x, 5 ]

[ 6, 8, 8, 8 ]

Now if any cell holds water > mat[ 2 ][ 3 ] then it can flow out. So if any of the cells have a height less than ‘5’ then it can trap utmost ‘5’ volume water in it.

We have to maintain this minimum border height also so that it can be determined what volume of water we can store.

So the basic idea is we will find the boundary cell having minimum height. If any of its neighbor cells have a height less than the minimum border height then it can store water = difference between the height of cells and minimum border height Otherwise all the neighboring cells will be considered as boundary cells.

We will take a priority queue that will store the cell positions based on the height of each cell.

Initially, we will visit all the boundary cells and put them in the queue.

Now the front element of the queue will give the cell a minimum height.

Now visit the neighbors of the boundary cell having minimum height. Push all the neighbors to queue. If any cell has a height smaller than this boundary cell then it can trap water = difference between heights of this cell and minimum border height.

Whenever a front element of the queue is popped out, if the cell has a height of more than the minimum border height, then we will update the minimum border height.

Algorithm:

Initialize a ‘VISITED’ array that will keep track of all the visited cells.
Create a priority queue ‘Q’ that will store pair of ( int and pair )
Take a variable ‘RES’ to store the result.
Push all the border cells in the ‘Q’ and mark them as visited.
Take a variable ‘MINBH’ that will store minimum border height.
Run a loop while ‘Q’ is not empty.
- Store the height of the top cell of ‘Q’ in ‘CURRENTH’
- Store the coordinates of the top cell in ‘Q’ in ‘CURRENTX’ and ‘CURRENTY’.
- Update ‘MINBH’ as max of ‘MINBH’ and ‘CURRENTH’.
- Pop this top cell from ‘Q’
- Initialize a 2-D matrix ‘directions’ with values [ [ 0 1 ] , [ 0 -1 ] [ 1 0 ] [ -1 0 ] ] to visit all the neighbouring cells.
- Run a loop 'i' from 0 to 3 for all the directions.
  - NEWX = CURRENTX + DIRECTIONS[ i ][ 0 ]
  - NEWY = CURRENTY + DIRECTIONS[ i ][ 1 ]
  - If the cell at coordinates ‘NEWX’ and ‘NEWY’ is a valid cell and it is not visited yet, then push this cell to ‘Q’ and mark it as visited.
  - If the height of this cell at ‘NEWX’ and ‘NEWY’ is less than ‘MINBH’ then add (MINBH - MAT[ NEWX][ NEWY]) to ‘RES’
Return ‘RES’.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O( M*N ), where ‘M’ and ‘N’ are the dimensions of the given matrix.

We are using a priority queue that will store the cells of the matrix. So the space complexity is O(M*N).

Time Complexity: OtherExplanation:

O( M*N *log(M*N) ), where ‘M’ and ‘N’ are the dimensions of the given matrix.

We are maintaining a priority queue and inserting every cell of the matrix in it. Inserting M*N values in the priority queue will result in O( M*N *log(M*N) ) time complexity.

Python (3.5)

'''
    Time complexity: O(M * N * log(M * N))
    Space complexity: O(M * N)

    Where M and N are the dimensions of the given matrix.
'''

import heapq as hq

def trappingWater(matrix):

    # Storing dimensions of matrix.
    m = len(matrix)
    n = len(matrix[0])

    # Initialise the visited vector.
    visited = [[0 for i in range(n)] for j in range(m)]
    q = []
    # Initialise priority queue.
    hq.heapify(q)

    # Initialise variable to store result.
    res = 0

    # Start traversing.
    for i in range(m):

        for j in range(n):

            if(i == 0 or i == m - 1 or j == 0 or j == n - 1):

                # Push border cells into priority queue.
                hq.heappush(q, (matrix[i][j], i, j))

                # Mark them visited
                visited[i][j] = True

    # Initialise variable to store minimum border height.
    minBH = 0

    # Start traversing while priority queue is not empty.
    while(q):

        # Store height of top cell in queue.
        currentH = q[0][0]

        # Initialise coordinates of top cell.
        currentX = q[0][1]
        currentY = q[0][2]

        # Update minimum border height.
        minBH = max(minBH, currentH)

        # Pop the top element.
        hq.heappop(q)

        # Initialise vector to store directions.
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        # Visit allthe neighbours of current cell.
        for i in range(4):

            # Storing coordinates of neighbour cells.
            newX = currentX + directions[i][0]
            newY = currentY + directions[i][1]

            # If new coordinates poto valid cell and is not previously visited.
            if(newX >= 0 and newX < m and newY >= 0 and newY < n and visited[newX][newY] == False):

                # Push into the priority queue.
                hq.heappush(q, (matrix[newX][newY], newX, newY))

                # Mark as visited.
                visited[newX][newY] = True

                # If height less than minimum border height.
                if(matrix[newX][newY] < minBH):

                    # Update res.
                    res = res + (minBH - matrix[newX][newY])

    # Return res.
    return res

C++ (g++ 5.4)

/*

    Time complexity: O(M * N * log(M * N))

    Space complexity: O(M * N)



    Where M and N are the dimensions of the given matrix.

*/



#include



int trappingWater(vector < vector < int >> & matrix) {



    // Storing dimensions of matrix.

    int m = matrix.size();

    int n = matrix[0].size();



    // Initialise the visited vector.

    vector < vector < int >> visited(m, vector < int > (n, 0));



    // Initialise priority queue.

    priority_queue < pair < int, pair < int, int >> , vector < pair < int, pair < int, int >>> ,

        greater < pair < int, pair < int, int >>> > q;



    // Initialise variable to store result.

    int res = 0;



    // Start traversing.

    for (int i = 0; i < m; i++) {

        for (int j = 0; j < n; j++) {

            if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {



                // Push border cells into priority queue.

                q.push({matrix[i][j], {i, j}});



                // Mark them visited.

                visited[i][j] = true;

            }

        }

    }



    // Initialise variable to store minimum border height. 

    int minBH = 0;



    // Start traversing while priority queue is not empty.

    while (!q.empty()) {



        // Store height of top cell in queue.

        int currentH = q.top().first;



        // Initialise coordinates of top cell.

        int currentX = q.top().second.first;

        int currentY = q.top().second.second;



        // Update minimum border height.

        minBH = max(minBH, currentH);



        // Pop the top element.

        q.pop();



        // Initialise vector to store directions.    

        vector> directions {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};



        // Visit allthe neighbours of current cell.       

        for (int i = 0; i < 4; i++) {



            // Storing coordinates of neighbour cells.

            int newX = currentX + directions[i][0];

            int newY = currentY + directions[i][1];



            // If new coordinates point to valid cell and is not previously visited. 

            if (newX >= 0 && newX < m && newY >= 0 && newY < n && visited[newX][newY] == false) {



                // Push into the priority queue.

                q.push({ matrix[newX][newY], { newX, newY } });



                // Mark as visited.

                visited[newX][newY] = true;



                // If height less than minimum border height.  

                if (matrix[newX][newY] < minBH) {



                    // Update res.

                    res = res + (minBH - matrix[newX][newY]);

                }

            }

        }

    }



    // Return res.

    return res;

}

Java (SE 1.8)

/*
    Time complexity: O(M * N * log(M * N))
    Space complexity: O(M * N)

    Where M and N are the dimensions of the given matrix.
*/

import java.util.PriorityQueue;
import javafx.util.Pair;
import java.util.Collections;
import java.util.Comparator;

class customComparator implements Comparator>> {
    public int compare(Pair> o1,
        Pair> o2) {
        if (o1.getKey().equals(o2.getKey())) {
            Pair o1pair = o1.getValue();
            Pair o2pair = o2.getValue();
            if (o1pair.getKey().equals(o2pair.getKey())) {
                return o1pair.getValue() - o2pair.getValue();
            }
            return o1pair.getKey() - o2pair.getKey();
        }
        return o1.getKey() - o2.getKey();
    }
}

public class Solution {
    public static int trappingWater(int[][] matrix) {
        // Storing dimensions of matrix.
        int m = matrix.length;
        int n = matrix[0].length;

        // Initialise the visited vector.
        int[][] visited = new int[m][n];

        // Initialise priority queue.
        customComparator comp = new customComparator();
        PriorityQueue > > q = new PriorityQueue<>(comp);

        // Initialise variable to store result.
        int res = 0;

        // Start traversing.
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {

                    // Push border cells into priority queue.
                    Pair temp = new Pair(i, j);
                    Pair > temp2 = 
                        new Pair >(matrix[i][j], temp);
                    q.add(temp2);

                    // Mark them visited.
                    visited[i][j] = 1;
                }
            }
        }

        // Initialise variable to store minimum border height. 
        int minBH = 0;

        // Start traversing while priority queue is not empty.
        while (q.size() > 0) {

            // Store height of top cell in queue.
            int currentH = q.peek().getKey();

            // Initialise coordinates of top cell.
            int currentX = q.peek().getValue().getKey();
            int currentY = q.peek().getValue().getValue();

            // Update minimum border height.
            minBH = Math.max(minBH, currentH);

            // Pop the top element.
            q.remove();

            // Initialise vector to store directions.
            int[][] directions = new int[4][2];
            directions[0][0] = 0;
            directions[0][1] = 1;
            directions[1][0] = 0;
            directions[1][1] = -1;
            directions[2][0] = 1;
            directions[2][1] = 0;
            directions[3][0] = -1;
            directions[3][1] = 0;

            // Visit allthe neighbours of current cell.       
            for (int i = 0; i < 4; i++) {

                // Storing coordinates of neighbour cells.
                int newX = currentX + directions[i][0];
                int newY = currentY + directions[i][1];

                // If new coordinates point to valid cell and is not previously visited. 
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && visited[newX][newY] == 0) {

                    // Push into the priority queue.
                    Pair temp = new Pair(newX, newY);
                    Pair > temp2 = 
                        new Pair >(matrix[newX][newY], temp);
                    q.add(temp2);

                    // Mark as visited.
                    visited[newX][newY] = 1;

                    // If height less than minimum border height.  
                    if (matrix[newX][newY] < minBH) {

                        // Update res.
                        res = res + (minBH - matrix[newX][newY]);
                    }
                }
            }
        }

        // Return res.
        return res;
    }
}

Given an M * N matrix, where the value at any cell denotes the height of that cell in a 2-D elevation map. You need to find the volume of water that can be trapped within it.

Input Format:

Output Format:

Note:

Constraints:

Top ION Group Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in ION Group Software Developer