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 bulbs to to array reversal, companies are asking typical problem-based questions. coin change Another real-life or situational-based problem that is often asked in the coding interview is the trapping rainwater 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 rainwater problem is a situation-based problem where you have to calculate the water that can be trapped inside. The trapping rainwater problem Consider the problem statement: An integer array A [] is given, which consists of the non-negative integers that represent 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. However, 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. However, 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: Initialize 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 initialize 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 this 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 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: Initialize the left_max and the right_max array of the size N Consider the given variable mx = 0 Traverse it from left to 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 the DP approach. However, the stack approach is quite an improvement over it. The idea here would be to keep 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 algorithms 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, concepts like arrays, strings, binary trees, coin change, and other crucial concepts should be at your fingertips so that you can get your dream job. In this blog post, we have explained the knits and grits of trapping rainwater problems. Get the essence of its approaches with this tutorial and implement it in your next interview in an efficient way. Happy coding! Also published . here

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Tech Interview Tips: Solving The Trapping Rainwater Problem

Too Long; Didn't Read

@ishitajuneja

Credibility

RELATED STORIES