Waterfall Streams Time : O(w * h) Space : O(w) 1234567891011121314151617181920212223242526272829303132333435#include <vector>using namespace std;vector<double> waterfallStreams(vector<vector<double>> array, int source) { int n = array.size(), m = array[0].size(); vector<double> dp(m, 0.0); dp[source] = 100.0; for(int i = 0; i < n; i++) { vector<double> nxt(m, 0.0); double water = 0.0; for(int j = 0; j < m; j++) { if(i and array[i-1][j] == 1.0) water = 0.0; water += dp[j] / 2; if(array[i][j] == 0.0) { nxt[j] += water; water = 0.0; } } water = 0.0; for(int j = m - 1; j >= 0; j--) { if(i and array[i-1][j] == 1.0) water = 0.0; water += dp[j] / 2; if(array[i][j] == 0.0) { nxt[j] += water; water = 0.0; } } swap(nxt, dp); } return dp;}