You are given a two-dimensional array (a matrix) of potentially unequal height and width that contains only values of 0 and 1. Each 0 represents land, and each 1 represents part of a river. A river consists of any number of 1s that are either horizontally or vertically adjacent, but not diagonally adjacent. The number of adjacent 1s forming a river determine it's size.
Write a function that returns an array of the sizes of all rivers represented in the input matrix. The sizes do not need to be in any particular order.
const matrix = [
[1, 0, 0, 1, 0],
[1, 0, 1, 0, 0],
[0, 0, 1, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 1, 1, 0]
]
riverSizes(matrix) //should return [2, 1, 5, 2, 2] - It may help the interviewee to think of the matrix as a graph, where each node in the matrix has 4 neighboring nodes - up, down, left, right - that may be part of the same river
- Prompt the interviewee to think about how they might count all the adjacent
1s to a given node. How can they repeat this process to count all the1s in a single river? This can be done recursively or using a stack. Today we will focus on using Depth First Search (DFS) - an algorithm that traverses a graph in a depthward motion and uses a stack. - If the interviewee has not yet considered a way to keep track of what nodes they have already visited; remind them that this is likely necessary to avoid repeating visits to a node
Note: Talk to the interviewer about some type of validation to make sure that i and j are valid inputs, making sure that all edge cases are factored in - i.e. the nodes above, below, to the left and to the right. There is a helper function provided below if your interview is having too much trouble with that. But make sure it is discussed.
Note: The recusive solution shown mutates the input array and the iterative approach shown does not. This is to demonstrate different approaches to the problem. An interviewee's solution can be any combination of impure/pure and recursive/iterative.
Strategy: Keep track of which nodes in the matrix have already been visited. Then traverse through each element in the matrix. If the node has been visited before, move on. Otherwise visit the node and if it is a river, add its unvisited neighbors to a stack. Update as each node is visited.
Time Complexity:
O(wh) where w is width and and h is height of the matrix. We visit every node once as we iterate through the array, which gives us O(w*h). We have the possibility of visiting each node up to four additional times. This is due to the fact that at every node, we might need to check the four surrounding nodes to see if they might be part of a river. But note, checking a node is a constant time operation and we perform it at most four times. So time complexity is still O(wh).
Space Complexity:
O(wh) where w is width and and h is height of the matrix. This is due to the creation of the visitedNodes matrix, which is the same size as the input matrix.
function riverSizes(matrix) {
const sizes = [];
//copy the matrix and replace every value with false to keep track of visited nodes
const visited = matrix.map(row => row.map(value => false))
//Iterate through the matrix
for (let i = 0; i < matrix.length; i++){ // row
for (let j = 0; j < matrix[i].length; j++) { // column
if (visited[i][j]) continue; // If we have looked at this node before skip; otherwise it's truthy and we should investigate it
traverseNode(i, j, matrix, visited, sizes) // Helper function #1
}
}
return sizes
}
function traverseNode(i, j, matrix, visited, sizes){
let currentRiverSize = 0;
const nodesToExplore = [[i, j]]; //Keep track of unvisited nodes that might be part of the same river we are investigating
// Implement depth first search to iterate through those potential river nodes 🎉
// Pushing nodes to the explore stack and popping them off as we check them
while (nodesToExplore.length){
const currentNode = nodesToExplore.pop(); //pop out the final value of the array
// set the current next node to the value at the location of these indices
i = currentNode[0];
j = currentNode[1];
//If we have looked at this node before, skip it. If not, mark it as visited.
if (visited[i][j]) continue;
// If not, set them as visited.
visited[i][j] = true;
if (matrix[i][j] === 0) continue; //If its a piece of land that we havent visited, skip - we do not want to visit the neighboring nodes of a piece of land - it is not part of our current river
//We now know we are dealing with an unvisited value node so we can update our counter
currentRiverSize += 1;
const unvisitedNeighbors = getUnvistedNeighbors(i, j, matrix, visited); // Gets all unvisited
for (let neighbor of unvisitedNeighbors) {// Gets the neighbor results from our second neighbor helper function
nodesToExplore.push(neighbor); // Push all unvisited neighbors so we can explore them (on to the stack)
}
}
if (currentRiverSize > 0){
sizes.push(currentRiverSize) // Add the river size to our Array
}
}Helper function #2 provided (if needed) below ↓
- this function confirms the validity of any neighbors - above, below, left and right
function getUnvistedNeighbors(i, j, matrix, visited){ // Only adds neighbors that are not visited
const unvisitedNeighbors = []
//Confirm that all neighbors are valid
if (i > 0 && !visited[i - 1][j]){
unvisitedNeighbors.push([i - 1, j]) // If the neighbor above exists and not visited
}
if (i < matrix.length - 1 && !visited[i + 1][j] ) { // Not in the bottom row and not visited
unvisitedNeighbors.push([i + 1, j])
}
if (j < 0 && !visited[i][j - 1]) { // Not in the left most column and not visited
unvisitedNeighbors.push([i, j - 1])
}
if (j < matrix[0].length - 1 && !visited[i][j + 1]) { // Not at the right most and not visited
unvisitedNeighbors.push([i, j+ 1])
}
return unvisitedNeighbors
}Strategy:
Traverse through each element in the matrix. If a node is land (0), skip it. If a node is part of a river (1) then recurse through that nodes neighbors to determine the river's size. An auxiliary structure is not used to keep track of visited nodes for this solution. Instead, the input matrix itself is mutated. A 0 now indicates either a land element or a node that has been previously visited. A 1 indicates an unvisited river node.
Time Complexity:
O(wh) where w is width and and h is height of the matrix. This is due to the same reasons cited in Solution 1.
Space Complexity:
O(wh) where w is width and and h is height of the matrix. This is due to the callstack. Consider a worst case situation in which every node is a part of the same river. The callstack would have a recursive function call for every node before resolving.
function riverSizes(matrix) {
const sizes = [];
//Iterate through the matrix. For a 0, move on. For a 1, stop to investigate.
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] === 1) {
//Investigate the river and add its size to our sizes array
sizes.push(visitRiver(matrix, i, j));
}
}
}
return sizes;
}
function visitRiver(matrix, i, j) {
//Base Case:
//Validate the i and j inputs first, then check if the node value is 0
if (i >= matrix.length || j >= matrix[0].length || i < 0 || j < 0 || !matrix[i][j]) return 0;
//Recursive Case:
//Mutate the current matrix element to a 0 to indicate it has been visisted
matrix[i][j] = 0;
//Recurse to the 4 directions around you & return the final size
return 1 + visitRiver(matrix,i+1,j) + visitRiver(matrix,i-1,j) + visitRiver(matrix,i,j+1) + visitRiver(matrix,i,j-1);
}