Max Entry Points in a cell


  • 0
    A

    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.


  • 0

    @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?


  • 0
    A

    @zzhai yes i also think same.


  • 0

    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;
    	}
    

  • 0

    @Tōsaka-Rin said in Max Entry Points in a cell:

    	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?


  • 0

    @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.


Log in to reply
 

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