River Sizes

• Time : O(n)
• Space : O(1)

#include <vector>
using namespace std;

int floodfill(vector<vector<int>>& matrix, int y, int x) {
	if(0 <= y and y < matrix.size() and 0 <= x and x < matrix[y].size() and matrix[y][x] == 1) {
		matrix[y][x] = 0;
		return 1 + floodfill(matrix, y + 1, x) + floodfill(matrix, y - 1, x) + floodfill(matrix, y, x + 1) + floodfill(matrix, y, x - 1);
	}
	return 0;
}

vector<int> riverSizes(vector<vector<int>> matrix) {
  vector<int> res;
	int n = matrix.size(), m = matrix[0].size();
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			if(matrix[i][j]) {
				res.push_back(floodfill(matrix,i,j));
			}
		}
	}
  return res;
}