## Rotten oranges problem

Rotten oranges problem goes like: In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;
• the value 1 representing a fresh orange;
• the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return `-1` instead.

```Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten because rotting only happens 4-directionally.
``` ## Thoughts

Rotting oranges problem offers a unique perspective on identifying a graph search problem. At first glance, it seems like the solution to the problem lies in changing the status of the given grid on multiple time steps while counting the steps and making sure that we come to a conclusion to our iterations, akin to solving a sudoku puzzle, where the state of the entire grid matters.

On further inspection though, we can see that we do not need to worry about the state of the entire grid, just the fresh oranges adjacent newly rotting oranges at each time step. We can consider the oranges as nodes of a graph, and the fresh oranges around them as connected to these nodes. We do not know the entire state of the graph beforehand, but we know that the adjacent nodes will expose themselves as time passes. This pushes us towards the idea of a Breadth-First Search, where we topologically move level by level through a graph.

This problem also has some interesting edge cases, with it being necessary to parse the graph to identify such cases:

### Show me the implementation

```class Solution:
def orangesRotting(self, grid: List[List[int]]) -&gt; int:
# Make sure we have a valid grid
if len(grid) &lt; 1 or len(grid) &lt; 1:
return -1
sources = []
ones = 0
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == 2:
sources.append((i, j))
elif grid[i][j] == 1:
ones += 1
if len(sources) == 0:
# In case of no rotten oranges, return value depending
# on the state of the grid
if ones == 0:
return 0
else:
return -1
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
# Grid is initially at t = -1
count = -1
visited = set(sources)
# End the BFS when there are no new sources left
while len(sources) &gt; 0:
count += 1
newsources = []
for source in sources:
i, j = source
grid[i][j] = 2
for direction in directions:
row = i + direction
col = j + direction
# Make sure it is a valid row and column,
# It is not visited, and it is a fresh orange
if row &gt;= 0 and row &lt; len(grid) \
and col &gt;= 0 and col &lt; len(grid) \
and (row, col) not in visited and grid[row][col] == 1:
newsources.append((row, col))
sources = newsources
# Make sure there are no fresh oranges left in the grid
for i in grid:
for j in i:
if j == 1:
return -1
return count
```

The runtime complexity of BFS is O(V + E), which in our scenario translates to moving to every node, i.e. O(n * m) where n and m are dimensions of the grid. The space complexity of BFS is O(V), which similarly as time complexity translates into O(n*m)

## Find friend groups

There are Nstudents in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if Ais a direct friend of B, and Bis a direct friend of C, then Ais an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the `i`th and `j`th students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students. For example,

```Input:
[[1,1,0,0,0,0],
[1,1,0,0,0,0],
[0,0,1,1,0,0],
[0,0,1,1,1,0],
[0,0,0,1,1,0],
[0,0,0,0,0,1]
]
Output: 3```

## Thought process

When we talk about the connections or relationships, we immediately will think of graph data structure. The node is the person and the edge is the relationship between two persons. So, first, we have to figure out whether it will be a directed graph or an undirected graph. In this problem, the friendship is a mutual relationship, thus the graph is undirected.

When you are reading this problem, the concept of Strongly Connected Components(SCC) will come into your mind. Ok, we will discuss why? If A is a friend of B, B is a friend of C, then A will be a friend of C. What does it mean? A is indirectly connected to C. It means that every friend can reach every other friend through a path if they are directly or indirectly connected. So in this way, they are forming a strong group or circle, in which every vertex is connected directly or indirectly in its group/circle. Notice that all friends (both direct and indirect), who should be in one friend circle are also in one connected component​ in the graph.

A particular group of friends is a single component. In this problem we are going to find out how many components are there in the graph. When you make a graph out of it. It will be like this(see below fig). It means there are 3 friends circles. We can solve this problem using 2 methods: depth first search and disjoint set method

## Using Depth first traversal method

Finding connected components for an undirected graph is very easy. We can do either BFS or DFS starting from every unvisited vertex, and we get all strongly connected components

```1. Initialize all nodes as not visited.
2. Initialize variable count as 1.
3. for every vertex 'v'.
(i) If 'v' is unvisited
Call DFS(v)
count=count+1
DFS(v)
1. Mark 'v' as visited.
2. Do following for every unvisited neighbor `u`
recursively call DFS(u)```

### DFS based approach implementation

```class Solution {
Public:
void DFS(int node,vector<vector<int>> edges,vecto<bool>visited)
{
int i;
visited[node]=true;
for(int i=0;i<edges[node].size();i++)
{
if(edges[node][i]==1 && node!=i && visited[i]==false)
{
DFS(i,edges,visited);
}
}
}

//Main Method
int findCircleNum(vector<vector<int>> edges) {
int i,j;

int n=edges.size();
int count=0;
vector<bool>visited(m);

//mark all the nodes as unvisited
for(i=0;i<n;i++)
{
visited[i]=false;
}

for(i=0;i<n;i++)
{
if(visited[i]==false)
{
DFS(i,edges,visited);
count=count+1;
}
}

return count;
}
};
```

Complexity

• Time Complexity: Since we just go along the edges and visit every node, it will be O(n).
• Space Complexity: O(n), to store the visited nodes.

## Using Disjoint Sets(Union Find)

So, how to think that this problem is solved by Disjoint Sets(union-find algorithm)?

The answer is simple because we need to keep track of the set of elements(here friends) partitioned into a number of non-overlapping subsets. Disjoint Sets(Union Find) always do this work very efficiently. We will use the Union by Rank algorithm to solve this problem.

To join two nodes, we will compare the rank of parents of both nodes.

• If the rank is equal, we can make any one of the parent’s node as a parent and increment the rank of the parent node by 1.
• If the rank is not same, then we can make the parent whose rank is greater than other. Let’s start solving this.

Union(1,2): 1 is a parent of itself and 2 is parent of itself. As both of them have different parents, so we have to connect them, and we will any of the parent as root, in this case we chose 1 and make it a parent. Union(2,1): 1 is a parent of itself and 1 is a parent of 2, as both of them have the same parents, already joined.

Union(3,4) :3 is a parent of itself and 4 is a parent of itself. Both of them have different parents, we need to join them. Union(4,3): 3 is parent of itself and 3 is the parent of 4. Both of them have the same parents, already joined.

Union(4,5):   3 is the parent node of 4 and 5 is the parent node of 5. Since parents are different, we have to compare the rank of the parents of both 4 and 5 nodes. 3 has higher rank then 5, it will be parent of 5 .(Used Path Compression) as shown in the below fig. Union(5,4): As now, 4 and 5 have the same parents, already joined. Last is the node 6 which connected to itself. So, nothing to do there. At the end of this exercise, we found that there are three different sets in the graph, and that is our answer of number of groups of friends in this graph or matrix.

### Disjoint set based approach implementation

```class Solution {
public:
class Node
{
public:
int data;
Node*parent;
int rank=0;
};
//make a set with only one element.
void make(int data)
{
Node*node=new Node();
node->data=data;
node->parent=node;
node->rank=0;
mapy[data]=node;
return;
}
map<int,Node*> mapy;
//To return the address of the particular node having data as `data`
Node*find(int data)
{
auto k=mapy.find(data);
if(k==mapy.end())
{
//There is no any node created, create the node
make(data);
return mapy[data];
}
else
{
return mapy[data];
}
return NULL;
}
/*Find the representative(parent) recursively and does path compression
as well*/
Node*parents(Node*node)
{
if(node->parent==node)
{
return node;
}
return node->parent = parents(node->parent);
}
//Main Method
int findCircleNum(vector<vector<int>>edges) {
int i,j;

vector<int> v;
int m=edges.size();
int n=edges.size();
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
if(edges[i][j]==1)
{
int a=i;
int b=j;

Node*A=find(a);
Node*B=find(b);

Node*PA=parents(A);
Node*PB=parents(B);

if(PA==PB)
{
}
else
{
if(PA->rank>=PB->rank)
{
//increment rank if both sets have Same rank
PA->rank=(PA->rank==PB->rank)?PA->rank+1:PA->rank;
PB->parent=PA;
}
else
{
PA->parent=PB;
}
}

}
}
}

int number=0;
for(auto k: mapy)
{
if(k.second->parent==k.second)
{
number=number+1;
}
}
return number;
}
};
```

Complexity

• Time Complexity: For each of the edge, we need to find the parents  and do the union, which is O(mlogn).
• Space Complexity: We used a map to store the parent information, O(n).

This post is contributed by Monika Bhasin

## Tarjan’s Algorithm to find strongly connected components

Tarjan Algorithm is a very useful algorithm in finding strongly connected components in a directed graph. What is a strongly connected component?

## What is Strongly Connected Component?

A directed graph is said to be strongly connected if we can reach any node from every other node in the graph. A strongly connected component of a directed graph is a subset of the nodes in the graph such that any two nodes of this subset are reachable from each other.
For any two nodes u and v in graph, if they are part of a strongly connected component, there exists a path from u to v and vice-a-versa.

For example, in the graph given below, there are 4 strongly connected components. There are two algorithms to strongly connected components one is Kosaraju’s algorithm and another one is the Tarjan algorithm.
Tarjan algorithm requires only one depth-first search traversal to find out all strongly connected components present in the graph. It is efficient as compared to Kosaraju’s algorithm as the other requires two DFS traversal.
An important thing to known to understand Tarjan’s algorithm is that depth-first traversal creates a DFS tree, meaning when we traverse a graph, it does traversal in a manner that a node is not visited again.

## Tarjan’s algorithm to find Strongly Connected Component?

Fundamental is very simple: From a node u if we can reach to any of its ancestors for any of its descendants (including itself), then there must be a cycle containing this node, all these nodes should be part of the same connected component.

For example, if x is the root of the tree and y is the descendant of x and there is an edge from y to another node z that is an ancestor of x, then we can say that edge y – Z together with the paths in the DFS tree from z to x and from x to z form a cycle, which must all be part of the same component. The edge from y to z is called back edge.

How can we know if there is a back-edge from a node to another? We keep track of two things for each node v of the graph:

```tin[v]: Represents the number of node visited before v in DFS.
low[v]: Represents smallest tin[x] of a node reachable by a back edge from the subtree of v.
```

The below figure displays tin[i] for each node. In the simplest way, it can be calculated as in-time of the node in depth-first traversal. The interesting part is how to calculate low[i]? To start with, low[i] is the node the node i itself. Going forward, for each node u, go through its neighbors:
1. If the neighbor v not already visited, that means, it is not a back edge. We will go forward and do the DFS on the v. Once DFS is finished, we will update the low[u] as follows:

low[u] = min(low[u], low[v]).

2. If the node v is already visited, that means there is a back edge from node v to any of the ancestor of node u. In that case, low[u] will be defined as follows

low[u] = min(low[u], tin[v]) For node v, if tin[v] == low[v], v is then the root of the next connected component. If you want to print nodes in strongly connected components, keep track of them on the stack. As soon as we get a node with low[i] == tin[i], pop all the nodes from the stack till we get the node i. All of these nodes belong to same SCC.

If low[v] > tin[u], we can say that node u and v belong to different SCCs and edge (u,v) is a bridge edge.

### Tarjan's algorithm to find strongly connected components

```package AlgorithmsAndMe;

import java.util.*;

public class TarjansAlgorithm {

Set<Integer> visited = new HashSet<>();
/* This map stores the time when the
current node is visited
*/
int [] tin;
/*
low will store minimum on
tin[v]
tin[p] for all p for which (v,p) is a back edge
low[to] for all to for which (v,to) is a tree edge
*/
int [] low;

//To maintain monotonic increasing order.
int timer;

void dfs(Graph g, int u, int parent, Stack<Integer> stack) {

//Put the current timer.
tin[u] = timer;
low[u] = timer;

stack.push(u);
timer++;

/*
Go through all the neighbors
*/
for (int to : g.getNeighbors(u)) {
//If it is parent, nothing to be done
if (to == parent) continue;

/* If the neighbor was already visited
get the minimum of the neighbor entry time
or the current low of the node.
*/
if (visited.contains(to)) {
low[u] = Math.min(low[u], tin[to]);
} else {
//Else do the DFS
dfs(g, to, u,stack);
/*
Normal edge scenario,
take the minimum of low of the parent and the child.
*/
low[u] = Math.min(low[u], low[to]);
}
}

System.out.println();
if (low[u] == tin[u]){
//Print the stack.
while(!stack.isEmpty() && stack.peek() != u){
System.out.print(stack.pop() + " ");
}
System.out.print(u + " ");
stack.pop();
}
}

public void findConnectedComponents(Graph g) {
timer = 0;
Stack<Integer> stack = new Stack<>();
Iterator it = g.getNodes().iterator();

tin = new int[g.getSize() + 1];
low = new int[g.getSize() + 1];
Arrays.fill(tin, Integer.MAX_VALUE);
Arrays.fill(low, Integer.MAX_VALUE);

while(it.hasNext()){
int i = (int) it.next();
if (!visited.contains(i))
dfs(g, i, -1, stack);
}
}
}
```

As we can see from the code that we only need one DFS traversal,therefore compexity of the algorithm will be O(|V| + |E|), where V and E are total number of vertex and edges present in the graph.

### Problems solved using algorithm

Please write to us if you need coaching for your interview preparations.

## Critical Connections in a Network

There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.
critical connection is a connection that, if removed, will make some server unable to reach some other server.
For example,
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted. Before going through this solution, I would strongly recommend reading Tarjan’s algorithm and find bridges in a graph problem.

```class Solution {
int timer;

List<List<Integer>> g;

boolean [] visited;
/* This map stores the time when the
current node is visited
*/
int [] tin;
int [] low;

void dfs(int u, int parent,
List<List<Integer>> res ) {
visited[u] = true;

//Put the current timer.
tin[u] = timer;
low[u] = timer;

timer++;

/*
Go through all the neighbors
*/
for (int to : g.get(u)) {
//If it is parent, nothing to be done
if (to == parent) continue;

/* If the neighbor was already visited
get the minimum of the neighbor entry time
or the current low of the node.
*/
if (visited[to]) {
low[u] = Math.min(low[u], tin[to]);
} else {
//Else do the DFS
dfs(to, u, res);
/*
Normal edge scenario,
take the minimum of low of the parent
and the child.
*/
low[u] = Math.min(low[u], low[to]);

/* If low of the child node is less than
time of entry of current node, then
there is a bridge.
*/
if (low[to] > tin[u]){
//List<Integer> l = new ArrayList<>();
List<Integer> l =
Arrays.asList(new Integer[]{u, to});
}
}
}

}

public void findBridges(List<List<Integer>> res) {
timer = 0;
for(int i=0; i<g.size(); i++){
if (!visited[i])
dfs(i, -1, res);
}
}

public List<List<Integer>> criticalConnections(int n,
List<List<Integer>> connections) {

g = new ArrayList<>();

visited = new boolean[n];
/* This map stores the time when the
current node is visited
*/
tin = new int[n];
low = new int[n];

Arrays.fill(visited, false);
Arrays.fill(tin, n);
Arrays.fill(low, n);

for(int i=0; i<n; i++){
}
for(List<Integer> l : connections){
}

List<List<Integer>> res = new ArrayList<>();
findBridges(res);

return res;

}
}
```

The complexity of this code is O(V + E) where V is number of vertices and E is number of edges in the graph.

If you want help with interview preparations, please feel free to book a free demo session with us.

Posted on 1 Comment on Critical Connections in a Network

## Matrix and graph traversals

Today, we will discuss an approach that can be used to solve quite a few problems with matrices. Problem structure is quite similar, you have a matrix, where cells represent real-world entities like land and water or oranges or walls and gates, etc. and we are asked to find something in that matrix. An example problem statement would be island problem. (taken from leetcode):

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. In this example, there are three islands.

Most of the time these problems have two entities, in the above example, its water and land. At first sight, this problem does not give any hint that it is a graph problem. For a problem to be a graph problem, it must have nodes and edges.

What are the nodes and edges of the graph?

One hint is to the relationship between the cells of the matrix. For example, in the island problem, 0s are water, and 1s are land. Land can be connected to land only which is adjacent to the land and a piece of land is isolated if surrounded by water from all four sides.

In this case, nodes seem to be the cells with value 1(land). Most of the time, in these kinds of problems, each cell of the matrix with a certain value is a node. If we have an n x m matrix, we are looking at n x m possible nodes. Also, here be aware that we are not interested in all the cells. Based on the problem statement, we can discard some cells. For example, in the island problem, we are interested in the cells which represent the land.

Now, what will be the edges? In these kinds of problems, a statement is given like an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. It means that a cell with value 1 is connected to neighbor cells only if they also contain 1.

Now that we know that cells containing 1 in the matrix are nodes of the graphs and connected to neighbors in they are also 1. To count the number of islands, all we have to do is find connected components in the graph. We reduced a matrix problem to a graph problem after all. Should we create an entire graph? Well no, at any point in time, we do not need the entire graph.

Traversals of graphs like DFS or BFS need a node and its neighbors.

If we are at a particular cell of a matrix, we already know the node. With the problem definition, we can know which other cells can be a neighbor of this node. So, we do not need to actually convert the matrix to a graph but just mimic the getNeighbor(Node u) function of a graph.

## Number of islands

The problem statement is given above as an example, we already identified the nodes and edges of the graph implicit in the matrix. We also know that to find the number of islands in the matrix, we have to find the number of connected components in the graphs as explained above. Which traversal can we use to find the number of connected components of a graph? It is a depth-first search problem.

```  public int numIslands(char[][] grid) {
int count = 0;
Set<Integer> visited = new HashSet<>();

int n = grid.length;

if(n <=0) return 0;
int m = grid.length;

for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
int cell = i * m + j;
if(!visited.contains(cell) && grid[i][j] == '1'){
count++;
dfs(i, j, visited, grid);
}
}
}
return count;
}

void dfs(int i, int j, Set<Integer> visited, char[][] a){

//Check if the node we are traversing is actually a valid node.
if(i<0 || i>=a.length
|| j<0 || j>=a.length
|| a[i][j] == '0') return;

int cell = i * a.length + j;
if(visited.contains(cell)) return;

//Visit neighbors
dfs(i+1, j, visited, a);
dfs(i-1, j, visited, a);
dfs(i, j+1, visited, a);
dfs(i, j-1, visited, a);
}
```

## Number of closed islands

There is another leetcode problem called Number of closed islands, it goes like:

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s. Return the number of closed islands.

Again, the similar structure of the problem, a matrix, cells representing the land and water. The only difference is now we have to find which land pieces are connected to the corners. Cells with 0s are lands, so cells with value 0 are our nodes. We will do a DFS starting from each of these nodes and see if we hit boundaries of the matrix, in that case, the node all these nodes cannot be closed islands.

```  int numClosedIslands(int[][] g){
int count = 0;
for(int i = 0;i < g.length;i++){
for(int j = 0;j < g.length;j++){
/* Our node is all the cells with
value zero, we will do a DFS from each node
*/
if(g[i][j] == 0){
count += dfs(g,i,j);
}
}
}
return count;
}

private int dfs(int[][] g,int row,int col){
//if we meet the edge return 0;
if(row < 0 || row >= g.length
|| col < 0 || col >= g.length){
return 0;
}
//if we meet 1 return 1;
if(g[row][col] == 1){
return 1;
}

/* This is to make sure that
we do not visit same node again and again
*/
g[row][col] = 1;

/* Make sure that we do not reach to the boundaries
doing DFS. */
int up = dfs(g,row-1,col);
int down = dfs(g,row+1,col);
int left = dfs(g,row,col-1);
int right = dfs(g,row,col+1);

//any of the sides meet the edge, is not an island;
return up & down & left & right;
}
```

## Walls and gates problem

There is another problem which falls under the same criteria, the problem is known as walls and gates problem

Given a m x n 2D grid initialized with these three possible values. -1 – A wall or an obstacle. 0 – A gate. INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF. In this problem, we have to find the distance to the room from gates and fill it with the minimum distance. Question number one, what are our nodes? In this problem, all the cells except the walls are nodes of the graph. Why walls are not nodes? Because one cannot go through the obstacles, so the cannot be part of the path of nodes, hence they cannot be considered as a node.

We can traverse horizontal and vertical, that means nodes at (i+1, j), (i-1, j), (i, j+1) and (i, j-1) are neighbors of cell (i,j) if they are a room or a gate.

To find the minimum distance from gates to a room, start a DFS from each gate and update the distance of the room with minimum distance seen so far. All we have to do it keep track of distance while starting from a gate.

```package AlgorithmsAndMe;

import java.util.HashSet;
import java.util.Set;

public class WallsAndGates {

public int[][] wallsAndGates(int[][] grid){

int n = grid.length;
if(n<=0) return new int;

int m = grid.length;

Set<Integer> visited = new HashSet<>();

for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
//This is our gate
if(grid[i][j] == 0){
dfs(i, j, grid, 0, visited);
}
}
}

return grid;
}

private void dfs(int x, int y, int[][] grid,
int distance, Set<Integer> visited){

int cellId = x*grid.length + y;
if(x<0 || x>=grid.length
|| y<0 || y>grid.length
|| grid[x][y] == -1
|| visited.contains(cellId)){
return;
}

//Mark as visited for this round.

//update the distance
grid[x][y] = Math.min(grid[x][y], distance);

dfs(x+1, y, grid, distance+1,visited);
dfs(x-1, y, grid, distance+1, visited);
dfs(x, y+1, grid, distance+1, visited);
dfs(x, y-1, grid, distance+1, visited);

//Mark unvisited for the next round.
visited.remove(cellId);

}
}
```

## Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’. A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

In this problem, again all the cells with zero are nodes, and edges are between the horizontal and vertical neighbors nodes. To capture all the nodes which are not connected to the edge of the matrix, first, find out which all are actually connected to the edge and mark them. Once we know all the nodes which are connected to the edge of the matrix, we can capture the nodes which are not connected.
To do so, we will start with nodes at the edge of the matrix and find the connected component of it and mark all the nodes in that connected component.

``` public void solve(char[][] grid) {
int n = grid.length;
if(n<=0) return;

int m = grid.length;

//Cover the first and last rows.
for(int j=0; j<m; j++){
if(grid[j] == 'O') dfs(0, j, grid);
if(grid[n-1][j] == 'O') dfs(n-1, j, grid);
}

//Cover the first and last columns.
for(int i=0; i<n; i++){
if(grid[i] == 'O') dfs(i, 0, grid);
if(grid[i][m-1] == 'O') dfs(i, m-1, grid);
}

for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j] == 'O') grid[i][j] = 'X';
if(grid[i][j] == '1') grid[i][j] = 'O';
}
}

return;
}

private void dfs(int x, int y, char[][] grid){

/* If we reach the edge of the node, return
Or we hit 'X', in that case, we cannot move
further in that direction.
*/
if(x<0 || x>=grid.length
|| y<0 || y>=grid.length
|| grid[x][y] == 'X'){
return;
}

if(grid[x][y] == 'O') {
grid[x][y] = '1';

dfs(x + 1, y, grid);
dfs(x - 1, y, grid);
dfs(x, y + 1, grid);
dfs(x, y - 1, grid);
}
}

```

The time complexity of all the solutions mentioned above is O(n * m) where n and m are rows and columns of the matrix. Because we will visit each cell at least once.
Please share if there is something wrong or missing. If you are preparing for an interviews and need help with it, please book a free session with us.

## Cycle in undirected graph using disjoint set

In post disjoint set data structure, we discussed the basics of disjoint sets. One of the applications of that data structure is to find if there is a cycle in a directed graph.

In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.

For example, in the graph shown below, there is a cycle formed by path : 1->2->4->6->1. Disjoint-set data structure has two operations: union and find. Union operation merges two sets into one, whereas find operation finds the representative of the set a given element belongs to.

### Using disjoint set to detect a cycle in directed grah

How can use the data structure and operations on it to find if a given directed graph contains a cycle or not?

We use an array A, which will store the parent of each node. Initialize the array with the element itself, that means to start with every node is the parent of itself.

Now, process each `edge(u,v)` in the graph and for each edge to the following: Get the root of both vertices u and v of the edge. If the roots of both nodes are different, update the root of u with the root of v. If roots are same, that means they belong to the same set and hence this edge creates a cycle.

How can we find the root of a vertex? As we know A[i] represents the parent of i; we start with i= u and go up till we find A[i] = i. It means there is no node parent of i and hence i is the root of the tree to which u belongs.

Let’s take an example and see how does it work. Below is the given directed graph and we have to if there is a cycle in it or not?  Now, we process each node of the graph one by one. First is `edge(1,2)`. The root of `node(1)` is 1 and the root of `node(2)` is 2. Since the roots of two vertices are different, we update the parent of the root of 2 which is A to the root of 1 which is 1. Next, we process `edge(2,3)`, here root of the `node(2)` is 1, whereas the root `node(3)` is 3. Again they differ, hence update A[root of 3] with root 2, i.e A = 1; Now, process `edge(2,4)`, it will end up with A = 1, can you deduce why? And similarly `edge(4,6)` will also lead to update A = 1. Now, we process the `edge(6,1)`. Here, root of `node(6)` is 1 and also the root of `node(1)` is 1. Both the nodes have same root, that means there is a cycle in the directed graph. #### To detect a cycle in direct graph : Implementation

```package com.company.Graphs;

import java.util.*;

/**
* Created by sangar on 21.12.18.
*/
private Map<Integer, ArrayList<Integer>> G;
private boolean isDirected;
private int count;

this.G = new HashMap<>();
this.isDirected = isDirected;
}

public void addEdge(int start, int dest){

if(this.G.containsKey(start)){
}else{
this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
}

if(!this.G.containsKey(dest)) {
this.G.put(dest, new ArrayList<>());
}
//In case graph is undirected
if(!this.isDirected) {
}
}

public boolean isEdge(int start, int dest){
if(this.G.containsKey(start)){
return this.G.get(start).contains(dest);
}

return false;
}

public boolean isCycleWithDisjointSet() {
int[] parent = new int[this.G.size() + 1];

for (int u = 1; u < this.G.size() + 1; u++) {
//Process edge from each node.

//Find root of u
int i, j;

//Worst complexity is O(V)
for(i=u; i != parent[i]; i = parent[i]);

/*This loop will run for O(E) times for all
the vertices combined. */
for(int v: this.G.get(u)){
for(j=v; j != parent[j]; j = parent[j]);

if(i == j){
System.out.println("Cycle detected at
("+ u + "," + v + ")");
return true;
}

parent[i] = j;
}
}
return false;
}
}
```

Test cases

```package test.Graphs;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 21.12.18.
*/
@Test
public void detectCycleInDirectedGraphTest() {

assertEquals(true, tester.isEdge(3,4));
assertEquals(false, tester.isEdge(1,4));

assertEquals(true, tester.isCycleWithDisjointSet());

}
}

```

Complexity of this algorithm is `O(EV)` where E is number of edges and V is vertices, where as union function in disjoint set can take linear time w.r.t to vertices and it may run for number of edge times.

Please share if there is something wrong or missing. If you are preparing for interview and interested in personalized coaching, please signup for free demo class.

## Disjoint set data structure

A disjoint set data structure or union and find maintains a collection 𝑆 = { 𝑆1, 𝑆2, ⋯ , 𝑆𝑛 } of disjoint dynamic sets. Subsets are said to be disjoint if intersection between them is NULL. For example, set {1,2,3} and {4,5,6} are disjoint sets, but {1,2,3} and {1,3,5} are not as intersection is {1,3} which is not null. Another important thing about the disjoint set is that every set is represented by a member of that set called as representative.

Operations on this disjoint set data structure:
1. Make Set: Creates a new set with one element x, since the sets are disjoint, we require that x not already be in any of the existing sets.
2. Union: Merges two sets containing x and y let’s say Sx and Sy and destroys the original sets.
3.Find: Returns the representative of the set which element belongs to.

Let’s take an example and see how disjointed sets can be used to find the connected components of an undirected graph.

To start with, we will make a set for each vertex by using make-set operation.

```for each vertex v in G(V)
do makeSet(v)
```

Next process all the edges in the graph (u,v) and connect set(u) and set(v) if the representatives of the set which contains u and set which contains v are not same.

```for each edge (u,v) in 𝐺(E)
do if findSet(u) != findSet(v)
then union(u, v)
```

Once above preprocessing steps have run, then we can easily find answer if two vertices u and v are part of same connected component or not?

```boolean isSameComponent(u, v)
if findSet(u)==findSet(v)
return True
else
return False
```

To find how many components are there, we can look at how many disjoint sets are there and that will give us the number of connected components in a graph. Let’s take an example and see how it works. Below table shows the processing of each edge in the graph show figure above. Now, how can we implement sets and quickly do union and find operations? There are two ways to do it.

### Disjoint set representation using an array

Simple implementation of disjoint set is using an array which maintains their representative of element i in A[i]. To this implementation to work, it is must that all the element in the set are in range 0 to N-1 where N is size of the array.

Initially, in makeSet() operation, set `A[i]=i`, for each i between 0 and N-1 and create the initial versions of the sets. ```for (int i=0; i<N; i++) A[i] = i;
```

Union operation for the sets that contain integers u and v, we scan the array A and change all the elements
that have the value A[u] to have the value A[v]. For example, we if want to connect an edge between 1 and 2 in the above set, the union operation will replace A with A. Now, if want to add an edge between 3 and 1. In this case, u = 3 and v = 1. A = 3 and A = 1. So, we will replace all the indices of A where A[i] = 1. So final array looks like this. Similarly, if want to add an edge from 6 to 7. ```//change all elements from A[u] to A[v].
void union(int A[], int u, int v){
int temp = A[u];
for(int i=0; i<A.length; i++){
if(A[i] == temp)
A[i] = A[v];
}
}
```

findSet(v) operation returns the value of A[v].

```int findSet(int A[], int v){
return A[v]
}
```

The complexity of makeSet() operation is `O(n)` as it initializes the entire array. Union operation take every time `O(n)` operations if we have to connect n nodes, then it will be `O(n2)` operations. FindSet() operation has constant time complexity.

We can represent a disjoint set using linked list too. In that case, each set will be a linked list, and head of the linked list will be the representative element. Each node contains two pointers, one to its next element it the set and other points to the representative of the set.

To initialize, each element will be added to a linked list. To union (u, v), we add the linked list which contains u to end of the linked list which contains v and change representation pointer of each node to point to the representation of list which contained v.

The complexity of union operation is again `O(n)`. Also, find operation can be `O(1)` as it returns the representative of it.

### Disjoint set forest

The disjoint-forests data structure is implemented by changing the interpretation of the meaning of the element of array A. Now each A[i] represents an element of a set and points to another element of that set. The root element points to itself. In short, A[i] now points to the parent of i.

Makeset operation does not change, as to start with each element will be the parent of itself.
Union operation will change, if we want to connect u and v with an edge, we update A[root of u] with the root of v. How to find the root of an element? As we have the relationship that A[i] is the parent of i, we can move up the chain until we find a case where `A[i] == i`, that case, i is the root of v.

```//finding root of an element
int root(int A[],int i){
while(A[i] != i){
i = A[i];
}
return i;
}

/*Changed union function where we connect
the elements by changing the root of
one of the elements
*/

int union(int A[] ,int u ,int v){
int rootU = root(A, u);
int rootV = root(A, v);
A[rootU] = rootV ;
}
```

This implementation has a worst-case complexity of `O(n)` for union function. And also we made the worst complexity of findSet operation as `O(n)`.

However, we can do some ranking on the size of trees which are being connected. We make sure that always root of smaller tree point to the root of the bigger tree.

```void union(int[] A, int[] sz, u, v){

//Finding roots
for (int i = u; i != A[i]; i = A[i]) ;
for (int j = v; j != A[j]; j = A[j]) ;

if (i == j) return;
//Comparing size of tree to put smaller tree root under
// bigger tree's root.
if (sz[i] < sz[j]){
A[i] = j;
sz[j] += sz[i];
}
else {
A[j] = i;
sz[i] += sz[j];
}
}
```

In the next few posts, we will be discussing applications of this method to solve different problems on graphs.
Please share if there is something wrong or missing. If you are preparing for an interview, and want coaching sessions to prepare for it, please signup for free demo session.

Posted on Categories Algorithms, Graph1 Comment on Disjoint set data structure

## Lowest common ancestor(LCA) using RMQ

We already have discussed lowest common ancestor and range minimum query. In this post, we will discuss how to use RMQ to find the lowest common ancestor of two given nodes in a binary tree or binary search tree. LCA of two nodes u and v is the node which is furthest from root and u and v are descendant of that node. For example, LCA `node(5)` and `node(9)` in below tree is `node(2)`. In earlier solutions, we scan the whole binary tree every time we have to find LCA of two nodes. This has a complexity of `O(n)` for each query. If this query if fired frequently, this operation may become a bottleneck of the algorithm. One way to avoid processing all nodes on each query is to preprocess binary tree and store precalculated information to find LCA of any two nodes in constant time.

This pattern is very similar to a range minimum query algorithm. Can we reduce the lowest common ancestor problem to range minimum query problem?

### Reduction of lowest common ancestor problem to RMQ

Let’s revise what is RMQ: Given an array A of length n; RMQ(i,j) – returns the index of the minimum element in the subarray A[i..j]. Let’s find LCA of two nodes 5 and 8 manually in the above binary tree. We notice that LCA(u,v) is a shallowest common node (in terms of distance from root) which is visited when u and v are visited using the depth-first search of the tree. An important thing to note is that we are interested in shallowest, which is minimum depth, the node between u and v. Sounds like RMQ?

Implementation wise, the tree is traversed as Euler tour, which means we visit each node of tree, without lifting the pencil. This is very similar to a preorder traversal of a tree. At most, there can be 2n-1 nodes in Euler tour of a tree with n nodes, store this tour in an array `E[1..2n-1]`.

As algorithm requires the shallowest node, closest to root, so we store the depth of each node while doing Euler tour, so we store the depth of each node in another array D[1..2n-1].

We should maintain the value when the node was visited for the first time. Why?

E[1..2n-1] – Store the nodes visited in a Euler tour of T. Euler[i] stores ith node visited in the tour.
D[1..2n-1] – Stores level of the nodes in tour. D[i] is the level of node at Euler[i]. (level is defined to be the distance from the root).
F[1..n] – F[i] will hold value when node is first visited.

For example of this graph, we start from node(1) and do Euler tour of the binary tree. Euler tour would be like Depth array is like First visit array looks like To compute LCA(u,v): All nodes in the Euler tour between the first visits to u and v are `E[F[u]...F[v]]` (assume F[u] is less than F[v] else, swap u and v). The shallowest node in this tour is at index `RMQ D(F[u]..F[v])`, since D[i] stores the depth of node at E[i].
RMQ function will return the index of the shallowest node between u and v, thus output node will be `E[RMQ D(F[u], F[v])]` as LCA(u,v)

Let’s take an example, find the lowest common ancestor of `node(5)` and `node(8)`.

First of all, find the first visit to `node(5)` and `node(8)`. It will be F which is 2 and F which is 7. Now, all the nodes which come between visit of `node(5)` and `node(8)` are in E[2..7], we have to find the shallowest node out these nodes. This can be done by applying RMQ on array D with range 3 to 6. LCA will be E[RMQ( D(2,7)], in this case, RMQ(D[2..7]) is index 3. E = 2, hence LCA(5,8) is `node(2)`. #### Lowest common ancestor using RMQ: Implementation

```package com.company.BST;

import java.util.Arrays;

/**
* Created by sangar on 1.1.19.
*/
public class LowestCommonAncestor {

private int[] E;
private int[] D;
private int[] F;

int[][] M;

private int tourCount;

public LowestCommonAncestor(BinarySearchTree tree){
//Create Euler tour, Depth array and First Visited array
E = new int[2*tree.getSize()];
D = new int[2*tree.getSize()];
F = new int[tree.getSize() + 1];

M = new int[2 * tree.getSize()][2 * tree.getSize()];

Arrays.fill(F, -1);
getEulerTour(tree.getRoot(), E, D, F, 0);

preProcess(D);
}

public int findLowestCommonAncestor(int u, int v){
//This means node is not in tree
if(u >= F.length || v >= F.length || F[u] == -1 || F[u] == -1)
return -1 ;

return E[rmq(D, F[u], F[v])];
}

/* This function does all the preprocessing on the tree and
creates all required arrays for the algorithm.
*/
private void getEulerTour(TreeNode node, int[] E, int[] D, int[] F,
int level){
if(node == null) return;

int val = (int)node.getValue();

E[tourCount] = val; // add to tour
D[tourCount] =  level; // store depth

if(F[val] == -1) {
F[(int) node.getValue()] = tourCount;
}
tourCount++;

if(node.getLeft() != null ) {
getEulerTour(node.getLeft(), E, D, F, level + 1);

E[tourCount] = val;
D[tourCount++] = level;
}
if(node.getRight() != null ) {
getEulerTour(node.getRight(), E, D, F, level + 1);

E[tourCount] = val;
D[tourCount++] = level;
}
}

/*
This function preprocess the depth array to quickly find
RMQ which is used to find shallowest node.
*/
void preProcess(int[] D) {

for (int i = 0; i < D.length; i++)
M[i] = i;

for (int j = 1; 1 << j <D.length ; j++){
for (int i = 0; i + (1 << j) - 1 < D.length; i++){
if (D[M[i][j - 1]] < D[M[i + (1 << (j - 1))][j - 1]])
M[i][j] = M[i][j - 1];
else
M[i][j] = M[i + (1 << (j - 1))][j - 1];
}
}
}

private int rmq(int a[], int start, int end){
int j = (int)Math.floor(Math.log(end-start+1));

if ( a[ M[start][j] ] <= a[M[end-(1<<j)+1][j]] )
return M[start][j];

else
return M[end-(1<<j)+1][j];
}
}
```

The beauty of this algorithm is that it can be used to find LCA of any tree, not just only binary tree or BST. The complexity of the algorithm to find a lowest common ancestor using range minimum query is `(O(n), O(1))` with an additional space complexity of `O(n)`.

Please share if there is something wrong or missing. If you are preparing for an interview, please signup for free demo class to guide you through the process.

Posted on Categories Algorithms, Binary Search Tree, Data Structures, GraphLeave a comment on Lowest common ancestor(LCA) using Range Minimum Query(RMQ)

In the last post, we discussed depth first traversal of a graph. Today, we will discuss another way to traverse a graph, which is breadth first traversal. What is breadth first traversal? Unlike depth-first traversal, where we go deep before visiting neighbors, in breadth-first search, we visit all the neighbors of a node before moving a level down. For example, breadth first traversal of the graph shown below will be [1,2,5,3,4,6] In breadth first search, we finish visiting all the nodes at a level before going further down the graph. For example, the graph used in the above example can be divided into three levels as shown. We start with a node in level 1 which is `node(1)`. Then visit all the nodes which are one level below `node(1)` which are `node(2)` and `node(5)`. Then we visit all the node at level 3 which are `node(3)`, `node(4)` and `node(6)`.

1. Start with the given node u, put node u to queue
2. While queue is not empty, repeat below steps:
1. Dequeue fro queue and print node u.
2. For each neighbor of u, node v
3. If v is not visited already: add v to the queue
4. mark v as visited

Let’s take an example and see how it works. Below is the graph and we have to find BFS for this graph. We start from `node(1)`, and put it in the queue. While the queue is not empty, we should pop from it and print the node. In this case, `node(1)` will be printed. Next, we go through all the neighbors of `node(1)` and put all the unvisited node on the queue. `node(2)` and `node(5)` will go on to the queue and marked as visited. Traversal = {1} Again, we dequeue from the queue and this time we get `node(2)`. We print it and go for all the neighbor node, `node(3)` and `node(4)` and mark them as visited. Traversal = {1,2} `node(5)` is dequeued next and printed. Here, even though `node(4)` is a neighbor of `node(5)`, it is already visited and hence not put on to the queue again. But `node(6)` is not yet visited, so put it on to the queue. Traversal = {1,2,5} Now, we pop `node(3)` and print it, however, `node(4)` is already visited. Hence, nothing is added to the queue. Traversal = {1,2,5,3} Next, `node(4)` is taken out from queue and printed, nothing goes on to queue. Traversal = {1,2,5,3,4} Last, we pop `node(6)` and print it. Traversal = {1,2,5,3,4,6}. At this point, the queue is empty and we stop traversal.

```public ArrayList<Integer> breadthFirstTraversal(){

boolean[] visited = new boolean[this.G.length];
ArrayList<Integer> traversal = new ArrayList<>();

//This is start node
visited = true;

while(!q.isEmpty()){
int u = (int)q.remove();

for(int i=1; i< this.G.length; i++){
if(this.G[u][i] && !visited[i]){
visited[i]= true;
}
}
}
System.out.println(traversal);
return traversal;

}
```

The complexity of this code is `O(V2)` as at least V nodes will go in queue and for each nodes internal for loop runs V times.

```  public ArrayList<Integer> breadthFirstTraversal(){

boolean[] visited = new boolean[this.G.size()];
ArrayList<Integer> traversal = new ArrayList<>();

//This is start node
visited = true;

//This loop will run for V times, once for each node.
while(!q.isEmpty()){
int u = (int)q.remove();

/*This loop has a worst-case complexity of O(V), where
node has an edge to every other node, but
the total number of times this loop will run is E times
where E number of edges.
*/
for(int v : this.G.get(u)){
if(!visited[v]){
visited[v]= true;
}
}
}
System.out.println(traversal);
return traversal;

}
```

The complexity of Breadth First Search is `O(V+E)` where V is the number of vertices and E is the number of edges in the graph.

The complexity difference in BFS when implemented by Adjacency Lists and Matrix occurs due to this fact that in Adjacency Matrix, to tell which nodes are adjacent to a given vertex, we take `O(|V|)` time, irrespective of edges. Whereas, in Adjacency List, it is immediately available to us, takes time proportional to adjacent vertices itself, which on summation over all vertices |V| is |E|. So, BFS by Adjacency List gives `O(|V| + |E|)`.

StackOverflow

When a graph is strongly connected, `O(V + E)` is actually `O(V2)`

### Applications of Breadth first traversal

1. To find shortest path between two nodes u and v
2. To test bipartite-ness of a graph
3. To find all nodes within one connected component

Please share if there is something wrong or missing. If you are preparing for an interview and want a free coaching session to guide you through it, please reach out to us at [email protected]

Posted on Categories Algorithms, Data Structures, Graph3 Comments on Breadth First traversal

## Find bridges in graph

Given a direct graph, detect bridges in the graph.

An edge is called as bridge edge if and only if on removal of that edge will increases number of components increase by one.

For example, in the below graphs, bridges are shown in green The concept of detecting bridges in a graph will be useful in solving the Euler path or tour problem.

Depth First Search of graph can be used to see if graph is connected or not. We can use the same concept, one by one remove each edge and see if the graph is still connected using DFS. If yes, then the edge is not bridge edge, if not, then edge is bridge edge.

However, this method entails quite a complexity of O(E * (V+E)) where E is number of edges and V is number of vertices.

Let’s think something better. Consider that we are looking at the edge (u,v) in a graph. In what condition, we can say that it is a bridge edge?
If we can somehow reach node u or any ancestor of u from any node which is a decedent of v, that means the graph is still connected and (u,v) is not a bridge edge. If the above condition is not possible, then (u,v) is the bridge.

How can we determine that there is no edge from decedent of v to u or its ancestor? For that we need to maintain time when a node was discovered during the depth-first search, call it tin[].

tin[u] is time when node u was discovered using DFS. If d[u] < d[v], means u was discovered before v.

Below is a graph with tin[u] filled for each node. Now, figure out the lowest tin[x] which can be reached from each node. Reason to find that is to see if there is a node x which is reachable from children of v and has tin[x] less than tin[u], i.e. x is ancestor of u reachable from children of v.

Store lowest DFS ancestor reachable from a node i in an array low[u].
low[u] = min(low[u], low[v])  for edge (u,v)

Idea here is that if (u,v) is an edge, then either there is no back edge from subtree of v to u and ancestor of u.
If there is a back edge to x from subtree of v, then minimum tin[x] reached by node in subtree will be assigned to the low[u].

The diagram shows the calculation of low[] in a graph. Finally, if low[v] > tin[u] that means if discovery time of u is less than least ancestor that can be reached from subtree of v, we have a bridge, because there is no way we can reach to an ancestor of u once we disconnect edge (u,v).

Lots of theory, let’s code it. We will be modifying Depth First Search implementation to keep track of tin[] and low[].

### Bridges in a graph implementation

```package AlgorithmsAndMe;

import java.util.*;

public class Bridges {

Set<Integer> visited = new HashSet<>();
/* This map stores the time when the
current node is visited
*/
Map<Integer, Integer> tin = new HashMap<>();

/*
low will store minimum on
tin[v]
tin[p] for all p for which (v,p) is a back edge
low[to] for all to for which (v,to) is a tree edge
*/
Map<Integer, Integer> low = new HashMap<>();

//To maintain monotonic increasing order.
int timer;

void dfs(Graph g, int u, int parent) {

//Put the current timer.
tin.put(u, timer);
low.put(u,timer);

timer++;

/*
Go through all the neighbors
*/
for (int to : g.getNeighbors(u)) {
//If it is parent, nothing to be done
if (to == parent) continue;

/* If the neighbor was already visited
get the minimum of the neighbor entry time
or the current low of the node.
*/
if (visited.contains(to)) {
low.put(u, Math.min(low.getOrDefault(u, Integer.MAX_VALUE),
tin.getOrDefault(to, Integer.MAX_VALUE)));
} else {
//Else do the DFS
dfs(g, to, u);
/*
Normal edge scenario,
take the minimum of low of the parent and the child.
*/
low.put(u, Math.min(low.getOrDefault(u, Integer.MAX_VALUE),
low.getOrDefault(to, Integer.MAX_VALUE)));

/* If low of the child node is less than
time of entry of current node, then
there is a bridge.
*/
if (low.get(to) > tin.get(u))
System.out.println(u + "->" + to);
}
}
}

public void findBridges(Graph g) {
timer = 0;
Iterator it = g.getNodes().iterator();
while(it.hasNext()){
int i = (int) it.next();
if (!visited.contains(i))
dfs(g, i, -1);
}
}
}
```

The complexity of finding bridges in a graph is O(V+E) where V is number of vertices and E is number of edges in graph.

Problems you can solve using this concept: