To enhance the standards of their hiring process, top tech-giants are enhancing the difficulty level of coding questions!
From array inversion problems to glowing bulb to coin change to array reversal, companies are asking typical problem-based questions.
Another real-life or situational based problem that is often asked in the coding interview is trapping rain water problem.
From Meta to Oracle, you may often come across this problem in most of the tech giant’s interviews.
If you want to excel at this problem, read our blog post where we are going to unfold certain approaches to solve this problem.
Let’s get started!
Trapping rain water problem
Trapping rain water problem is a situation-based problem where you have to calculate the water that can be trapped inside.
Consider the problem statement:
An integer array A [] is given which consists of the non-negative integers that represents an elevation map. The width of the bar is given as 1. Your task would be to compute the volume of water that needs to be trapped after the rain.
Input in this case would be; A [] = { 0, 1, 0,2, 1,0, 1,3, 2,1,2, 1]
The output in this case would be 6.
You can trap 1 unit of the input between the first and the third block. Although, you can trap the 4th unit of water between the given second and the third block.
The volume of water in this case would be 1+4+ 1 = 6
Algorithm to consider:
The basic key behind this approach is to better understand the rainwater which can be trapped only if the block of some great height exists on the left or the right side of a current block. The rainwater will get trapped on the top of your block.
Though, it can be inferred easily with the amount of water that is needed to be blocked or which can hold the minimum or the maximum height present on both the left or right side alongside the height of a current block.
Approaches to consider
Trapping rainwater problems can be solved with the help of certain approaches that you need to follow if you want to excel at this problem.
Brute Force Approach
In this approach, our main task would be to find out the minimum or the maximum height on the left or at the right of each given element. Here, you need to traverse all the elements simply with the array A[].
For all the elements, you may need to find the maximum height on both the left or right. Add mi{right_max, left_max} -A[i] to the given answer.
The steps to follow in this case are:
- Initialise the variable res till 0 to store the final answer
- Traverse the given array as A[] till 1 to N for each given element. To initialise the left_max as 0 you need the right_max as 0. Traverse from the A[i] till the beginning in order to update. Simply, you need to traverse from the A [i] till the end of your array in order to update.
The time complexity in thi =s case would be the O [n ^2]. For each given element, both the left and the right halves would be traversed. The space complexity in any case would be O[1]
Dynamic Programming Approach
This approach is also quite a wonderful approach to follow when it comes to solving the trapping rain water problem.
In a brute force approach, we traverse the elements from left to the right. What happens if we are able to store this information with the problem using single traversal for reducing the time complexity of the O[N].
The idea here would be to consider the two arrays which are max_left [] and max_right []. You need to store the maximum height with the left til the right index. Similarly the right_max [i] would store the desired height until it reaches the index i.
The algorithm to consider is:
- Initialise the left_max and the right_max array of the size N
- Consider the given variable mx = 0
- Traverse it from the left till right for each of the index i to update as the mx=max
- Similarly, you can traverse the given loop for the i index to update till mx = max for traversing it in an ideal way.
Stack Approach
The arrays are traversed twice in the case of DP approach. Though, the stack approach is quite an improvement over it.
The idea here would be to keep the track of current block A[i] in a way that all of the previous blocks will be of small height in a given array.
The algorithm to consider in this case are:
- Declare the stack as S
- Traverse a given array from left to right. In case the current block would be larger than the stack, it needs to be inferred at the top of a given stack. It shall be conferred between your current block that is larger than a top of stack
- Perform the s.pop{} to add the water that needs to be stored
- To calculate the total volume of the water, you need to calculate the length = current index i - S.top() -1
- The width in this case would be min [A [i] - A [S.top ()]
- Add the volume as the Length *width
As the array will be traversed once, the time complexity in this case would be the O[N]
The space complexity would also be O[N] as it takes up your space.
Wrapping Up
While preparing for a tech giant’s interview the concepts like arrays, strings, binary tree, coin change and other crucial concepts should be on your fingertips so that you can get your dream job.
In this blog post, we have explained the knits and grits of trapping rain water problems. Get the essence of its approaches with this tutorial and implement it in your next interview in an efficient way.
Happy coding!
No comments yet