Interviewing.io: 42. Trapping Rain Water | As an interviewee

Feb. 21, 2022

Introduction

I started to practice mock interview on interviewing.io since I have 27 peer mock interviews. Today I was asked to work on 42. Trapping Rain Water

My feedback

The interviewer asked to calculate the amount of trapping water given an array of integer. I did come out linear solution to calculate prefix and suffix, and then he asked me to calculate the water using given test case by hand. I did the calculation first, and then wrote the code, and tested the code to make it work. The interviewer asked me to come out space optimal solution using O(1) instead of O(N), he came out two pointer solution, and then explained it to me. After discussion, I tried to give counter example, and then I noticed that it is not necessary to find rightmost maximum if left maximum is smaller than current right one. I should have analyzed carefully for the constraint. The discussion was very relax, and interviewer gave me a lot of encouragement. Great thanks.

My algorithm

	using System;
	// To execute C#, please define "static void Main" on a class
	// named Solution.
	/*
	Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
	height = [0,1,0,2,1,0,1,3,2,1,2,1]
	prefix 0,0,1,1,2,2,2,2,3,3,3,3
	suffix 3,3,3,3,3,3,3,2,2.2,1.0
	water 0,0,1,0,1,2,1,0,0,1,0,0
	sum = 6
	go through min(0,3) > 0 ->
	O(N)
	[0,1,0,2,1]
	[3,1,2,5]
	- highest bar
	3 right 5 - min (3,5) = 1 water
	iterate the number in the array from left to right
	3
	1 -> 3, 5 , hold 3 -1 = 2
	2 -> 3, 5, hold 3 - 2 = 1
	5 -> 3, 0, < 5 -> 0
	sum = 3
	return 3
	*/
	class Solution
	{
	static void Main(string[] args)
	{
	var test = new Solution();
	var result = test.CalTrapWater(new int[]{0,1,0,2,1,0,1,3,2,1,2,1});
	// for (var i = 0; i < 5; i++)
	{
	Console.WriteLine("water is " + result.ToString());
	}
	}
	///[0, 1, 0, 2, 1] - line 19 to line 29 - return 3
	/// time: O(N)
	/// space: O(N)
	///
	public int CalTrapWater(int[] nums)
	{
	if(nums == null || nums.Length <= 2)
	return 0;
	var n = nums.Length;
	var prefix = new int[n]; // default 0
	var suffix = new int[n];
	//
	//
	var max = 0;
	for(int i = 0; i < n; i++) // i = 1
	{
	prefix[i] = Math.Max(max, nums[i]); // prefix[1] = 0, prefix[2] = 1, prefix[3] = 1, prefix[4] = 2
	max = prefix[i];
	}
	max = 0;
	for(int i = n -1 ; i >= 0; i--)
	{
	suffix[i] = Math.Max(max, nums[i]);// s[4] = 0, suffix[3] = 1, s[2] = 2, s[1] = 2, s[0] = 2
	max = suffix[i];
	}
	var water = 0;
	for(int i = 0; i < n; i++)
	{
	max = Math.Min(prefix[i], suffix[i]); //i = 2, water = 1,
	if(max > nums[i])
	water += max - nums[i];
	}
	return water;
	}
	}

view raw Leetcode42TrappingRainWater.cs hosted with ❤ by GitHub

Work on O(N) time complexity, O(1) space | Two pointers technique