Uber Interview Question

This problem was asked by Uber.

You are given a 2-d matrix where each cell consists of either /, \, or an empty space. Write an algorithm that determines into how many regions the slashes divide the space.

For example, suppose the input for a three-by-six grid is the following:

\    /
 \  /
  \/

Considering the edges of the matrix as boundaries, this divides the grid into three triangles, so you should return 3.

I have created a video with detailed solution walkthrough of the problem as well.

Before jumping on the problem, let’s visualize it by drawing on paper and pen how our problem would actually look like.

One assumption that I am making for this problem is that instead of spaces I will be considering . as my operator, so our matrix will look something like this:-

The slash lines divide our matrix into three regions as shown below:-

Now that we have a clear picture about the problem statement, let’s try to brainstorm what approach we can take.

Let’s assume I am at a cell (i,j), now standing there, I can take any of the 4 directions (i-1,j) , (i,j+1) , (i+1,j) , (i,j-1) .

Let’s note down our findings:-

1. If I am at a cell which has a \ or / (let’s call these kind of cells as block cells) then for sure I cannot traverse pass through it.
2. If I am at a cell other than the blocked cell, then I can traverse into 4 directions unless I encounter a blocked cell or step outside the matrix dimensions.
3. We can make use of an auxiliary 2-D matrix to keep track of which cells we have already visited, so that we don’t visit them again.

Let’s try to understand our traversal steps in terms of diagrams:-

1. We will use two for loops to traverse around the matrix, start at cell (0,0) and as it’s not being visited yet, we start our traversal but it’s a blocked cell, so nothing will happen.
2. Now we move to cell (0,1) , it’s an empty cell, so let’s mark it visited.

3. From (0,1) we can move into 4 directions, but from here we can only move into 1 directions , which is (0,2) and mark it visited.

4. Similarly now we are at (0,2) , from here we can move into 3 directions but (0,1) but it’s already visited, so we won’t traverse it and visit the other two directions and keep doing this process till we have covered the whole possible region, which would look something like the below image.

5. We will use a global counter to keep track of region count and we will increment it every time we have completed our traversal over a region.

Our final diagram will look something like this:-

The overall time complexity of the program will be O(n²) . As we will traverse over all the cells only once and total count of the cells is- n X m

Please look at the code written in c++ to understand the implementation of the code.