Max Entry Points in a cell

• Problem statement: You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves). The cells are named with an integer value from 0 to N-1. You need to find the following :

find Maximum number of entry points (incoming edges) for any cell in the maze

Note: Aim for O(N) solution.

INPUT FORMAT - First line has the number of cells N

Second line has list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell ‘i’ in one step. edge[i] is -1 if the ‘i’th cell doesn’t have an exit.

OUTPUT FORMAT - Find max entry points in any cell.

• @abhi96gupta

1 cell's exit is another cell's entry. Can we simply go through the edge list, and calculate each cell's in-degree?

• @zzhai yes i also think same.

• At first, I was thinking about doing a DFS then I also came up with indegree array. Heres are my code for implementation. Hope it helps.

``````public int findMaxEntryPoint(int n, int[] cells){
int m = cells.length;
if(m != n) return 0;
int[] indegree = new int[n];
Arrays.fill(indegree, 1);

// visit every cell and update the indegree for destination
for(int i = 0; i < n; i ++){
int dest = cells[i];
if(dest < n && dest != -1){
indegree[dest] ++;
}
}
// find the max entry point(s)
int max = Integer.MIN_VALUE;
for(int i = 0; i < n; i ++){
max = Math.max(max, indegree[i]);
}
return max;
}
``````

• ``````	Arrays.fill(indegree, 1);
``````

Help me understand this ? E.g. the maze only has 2 cells, A enters B, and B enters A. What are the in-degree's they have?

• @zzhai Since the problem statement did not tell us the intial start point, I assume that we can start from any cell which means the initial indegree for every cell should be one. Based on your case, maybe I should not do the initial setting and let them be 0.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.