We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
staticintfindShortest(intgraphNodes,int[]graphFrom,int[]graphTo,long[]ids,intval){// Start by finding all nodes of the target color.List<Integer>targetNodes=newArrayList<Integer>();for(inth=0;h<ids.length;h++){if(ids[h]==val)targetNodes.add(h);}for(intx:targetNodes){System.out.println(x);}//Set up visited indicator and placeholder min. path lengths.boolean[]visited=newboolean[graphNodes];int[]pathLengths=newint[targetNodes.size()];for(intl=0;l<pathLengths.length;l++)pathLengths[l]=-1;//Create the graph in the form of a list of neighbor node lists.List<List<Integer>>neighbors=newArrayList<List<Integer>>();for(inti=0;i<graphNodes;i++)neighbors.add(newArrayList<Integer>());for(intj=0;j<graphFrom.length;j++){intnodeFrom=graphFrom[j]-1;intnodeTo=graphTo[j]-1;neighbors.get(nodeFrom).add(nodeTo);neighbors.get(nodeTo).add(nodeFrom);}//Reset the visited boolean array for each target node. Then use DFS to find the shortest path to the nearest node of the same color.for(intk=0;k<targetNodes.size();k++){visited=newboolean[graphNodes];intnode=targetNodes.get(k);//System.out.println("Node " + node);DFS(neighbors,visited,ids,val,0,pathLengths,k,node);}//Lastly, find the shortest path if present by sorting the array and looking for the first non-negative number.Arrays.sort(pathLengths);for(intm=0;m<pathLengths.length;m++){//System.out.println(pathLengths[m]);if(pathLengths[m]>0)returnpathLengths[m];}return-1;}staticvoidDFS(List<List<Integer>>neighbors,boolean[]visited,long[]ids,intval,intlen,int[]pathLengths,intnode,intcurr){//System.out.println("START: Node " + node);visited[curr]=true;List<Integer>nodeNeighbors=neighbors.get(curr);if(ids[curr]==val&&len>0){//If the function isn't at the starting node and the current node is of the target color, update the path length for the starting node. If the starting node already has a path length assigned, pick the minimum of len and the previous path length.//System.out.println("MATCH: Node " + curr);if(pathLengths[node]==-1){//System.out.println("ADD: Node " + node);pathLengths[node]=len;}else{//System.out.println("UPDATE: Node " + node);pathLengths[node]=Math.min(pathLengths[node],len);}}//Run the DFS function recursively with all neighbors that haven't been visited yet, adding 1 to the previous path length.for(intneighbor:nodeNeighbors){if(!visited[neighbor]){//System.out.println("Node " + curr + " (" + ids[curr] + "), Neighbor " + neighbor);DFS(neighbors,visited,ids,val,len+1,pathLengths,node,neighbor);}}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
Find the nearest clone
You are viewing a single comment's thread. Return to all comments →
Java 8 solution (passes all test cases):