Find the nearest clone

  • + 0 comments

    Java 8 solution (passes all test cases):

    static int findShortest(int graphNodes, int[] graphFrom, int[] graphTo, long[] ids, int val) {
        // Start by finding all nodes of the target color.
        List<Integer> targetNodes = new ArrayList<Integer>();
        for (int h = 0; h < ids.length; h++) {
            if (ids[h] == val) targetNodes.add(h);
        }
        for (int x : targetNodes) {
            System.out.println(x);
        }
        //Set up visited indicator and placeholder min. path lengths.
    		boolean[] visited = new boolean[graphNodes];
        int[] pathLengths = new int[targetNodes.size()];
        for (int l = 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 = new ArrayList<List<Integer>>();
        for (int i = 0; i < graphNodes; i++) neighbors.add(new ArrayList<Integer>());
        for (int j = 0; j < graphFrom.length; j++) {
            int nodeFrom = graphFrom[j]-1;
            int nodeTo = 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 (int k = 0; k < targetNodes.size(); k++) {
            visited = new boolean[graphNodes];
            int node = 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 (int m = 0; m < pathLengths.length; m++) {
            //System.out.println(pathLengths[m]);
            if (pathLengths[m] > 0) return pathLengths[m];
        }
        
        return -1;
    }
    
    static void DFS(List<List<Integer>> neighbors, boolean[] visited, long[] ids, int val, int len, int[] pathLengths, int node, int curr) {
        //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 (int neighbor : nodeNeighbors) {
            if (!visited[neighbor]) {
            //System.out.println("Node " + curr + " (" + ids[curr] + "), Neighbor " + neighbor);
            DFS(neighbors, visited, ids, val, len+1, pathLengths, node, neighbor); }
        }
    }