The one dimensional twitter waterflow problem is this:

You are given an array that represents a hill in the sense that the ith entry is the height of the ith location of the hill. When it rains, water logs in the hills, and you need to figure out how much water would log.

For example, after raining, the array 2 5 3 4 3 2 5 5 3 4 2 2 2 looks like this,

and 9 units of water have accumulated.

The challenge is to solve the 2D version of this. To clarify, you will be given a 2D matrix of land heights, and you will have to output the total amount of rainwater it can collect. Water cannot flow out through diagonals, but only the four cardinal directions.

  • 1
    \$\begingroup\$ duplicate? \$\endgroup\$ – ngn Jul 1 '18 at 6:15
  • 3
    \$\begingroup\$ @AgnishomChattopadhyay Fair enough. I think you should mention big-O of what we should optimise for - the size of the matrix, or the volume of the water held, or the max height? \$\endgroup\$ – ngn Jul 1 '18 at 7:12
  • 2
    \$\begingroup\$ @AgnishomChattopadhyay also, it would be nice to have some tests \$\endgroup\$ – ngn Jul 1 '18 at 7:21
  • 4
    \$\begingroup\$ I think you should make it more obvious that the actual challenge is the second part of the post and give at least one 2D example. \$\endgroup\$ – Arnauld Jul 1 '18 at 7:47
  • 1
    \$\begingroup\$ Also: (1) if there is a winning criteria tag, don't need [code-challenge]. (2) best case, worst case or average case? \$\endgroup\$ – user202729 Jul 1 '18 at 9:33

Python 3, O(h × w × d) 296 bytes, O(h × w × d')

def f(a):
 w=0;b=[len(a[0])*[0]];a=b+a+b;a=[[0]+x+[0]for x in a];b=sorted(set(sum(a,[])))
 for[i,j]in zip(b,b[1:]+[1+max(b)]):
  while c:
   if x<len(a)and x>=0and y<len(a[0])and y>=0and a[x][y]<=i:w+=i-a[x][y];a[x][y]=j;c+=[[x+1,y],[x,y+1],[x-1,y],[x,y-1]]
 return w

Try it online! Where d' represents the number of distinct values in the input. Edit: Saved 3 bytes thanks to @Mr.Xcoder.

| improve this answer | |
  • \$\begingroup\$ (what is h, w and d?) \$\endgroup\$ – user202729 Jul 1 '18 at 10:01
  • \$\begingroup\$ @user202729 d is the highest land height in the w × h grid, but I like to think of it as the depth. \$\endgroup\$ – Neil Jul 1 '18 at 10:16
  • \$\begingroup\$ b=[len(a[0])*[0]] should work for 276. \$\endgroup\$ – Mr. Xcoder Jul 1 '18 at 12:31
  • \$\begingroup\$ Thanks for the answer. I'd like to think that there is some algorithm that is independent of d. Otherwise, scaling all the numbers by some arbitrary amount would randomly require more time. \$\endgroup\$ – Agnishom Chattopadhyay Jul 1 '18 at 15:28
  • \$\begingroup\$ @AgnishomChattopadhyay Better now? \$\endgroup\$ – Neil Jul 1 '18 at 16:03

Not the answer you're looking for? Browse other questions tagged or ask your own question.