Having two amazingly bright children is my greatest blessing, and this lockdown is giving me the opportunity to show them the type of work I do, which feels really nice :-)
This week the topic of breaking down a problem into smaller and simpler tasks came up, and with the help of some bowls, cups and a litre of water, I managed to get us all dripping wet and probably ruined the living room floor. Tess, on the other hand, made a very interesting observation about how the smaller cups would get filled first as the amount of water in the bowl raised to cover them.
The same key insight can be used to tackle the trapping rain water problem on Leetcode. We need to find our "cups" and calculate how much water they can hold given the water level of the "bowl" itself.
function solution(A) {
if (A.length < 2) return 0;
const sumIntermediateCols = (arr, h, g, start, end) => {
let sum = 0;
for (let i = start + 1; i < end; i++) sum += arr[i];
return h * g - sum;
}
const findNextCol = (arr, colIdx, colVal) => {
let max = 0;
for (let i = colIdx + 1; i < arr.length; i++) {
if (arr[i] >= colVal) {
return i; //return the next column at least as high as A[i]
} else {
max = Math.max(max, arr[i]); //track the highest remaining column
}
}
//return index of max if found, otherwise colIdx as last resort
return Math.max(arr.indexOf(max, colIdx), colIdx);
}
const calculator = (arr) => {
let raindrops = 0;
let gap = 0;
let height = 0;
let nextCol = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] > 0) {
nextCol = findNextCol(arr, i, arr[i]);
if (nextCol !== i) {
gap = nextCol - i - 1;
height = Math.min(arr[i], arr[nextCol]);
raindrops += sumIntermediateCols(arr, height, gap, i, nextCol);
i = nextCol - 1;
}
}
}
return raindrops;
}
return calculator(A);
}
They didn't ask me about the runtime complexity of the algorithm but I told them anyway. It's O(1) space and O(n) time and it ran in 56ms with 34.9MB of memory so it was better than what 91.38% of the other kids came up with. Not bad for a 7 year old!
Oldest comments (1)
It is a blessings to have kids, and specially brilliant kids who can provide ideas to solve leetcode hard problem! Great writeup! :) I also tried to re-explain the DP version here. You can have a look and let me know how it went! Thanks!