Tarjan's algorithm: use HashMap TLE but use Array beats 100%. Why??
My solution uses Tarjan\'s algorithm. However, if I use HashMap to represents the adjacency list of graph, the solution TLE; but if I use array to represents th
My solution uses Tarjan\'s algorithm. However, if I use HashMap to represents the adjacency list of graph, the solution TLE; but if I use array to represents the graph, the solution beats 100%. The big-O complexity of these two implementation should be the same. What\'s going on?\n\nThe only hypothesis I could think of is: when n gets very large, HashMap starts to have a lot of hash collision. But how to test this hypothesis?\n\n**The TLE test case is** \n```\n100000\n[[1,0],[2,0],[3,2],[4,0],[5,2],[6,3],[7,1],[8,5],[9,0],[10,8],........\n```\n\n**Implementation using HashMap** \n\n```\nclass Solution {\n    private int time = 0; // current time of discovery\n\n    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {\n        Map<Integer, List<Integer>> graph = new HashMap<>(); // node -> neighbors\n\n        for (List<Integer> conn : connections) {\n            int n1 = conn.get(0);\n            int n2 = conn.get(1);\n            graph.putIfAbsent(n1, new ArrayList<>());\n            graph.putIfAbsent(n2, new ArrayList<>());\n            graph.get(n1).add(n2);\n            graph.get(n2).add(n1);\n        }\n\n        int[] disc = new int[n]; // discovery time of each node\n        int[] low = new int[n]; // earliest discovered node reachable from this node in DFS\n        boolean[] visited = new boolean[n]; // whether this node has been visited in DFS\n        List<List<Integer>> out = new ArrayList<>();\n\n        dfs(0, -1, disc, low, visited, graph, out); // arbitrarily pick a node to start DFS\n\n        return out;\n    }\n\n    // root = current node under consideration\n    // parent = parent of current node\n    private void dfs(int root, int parent, int[] disc, int[] low, boolean[] visited, Map<Integer, List<Integer>> graph, List<List<Integer>> out) {\n        visited[root] = true;\n        disc[root] = time++;\n        low[root] = disc[root]; // we don\'t have to initialize low[] to inf because of this line\n\n        List<Integer> neighbors = graph.get(root);\n        if (neighbors == null) {\n            return;\n        }\n\n        for (Integer nei : neighbors) {\n            if (nei == parent) {\n                continue;\n            }\n\n            if (!visited[nei]) {\n                dfs(nei, root, disc, low, visited, graph, out);\n                low[root] = Math.min(low[root], low[nei]);\n                if (disc[root] < low[nei]) {\n                    out.add(Arrays.asList(root, nei));\n                }\n            } else {\n                low[root] = Math.min(low[root], disc[nei]);\n            }\n        }\n    }\n}\n```\n\n\n**Implementation using Array**\n\n\n```java\nclass Solution {\n    private int time = 0; // current time of discovery\n\n    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {\n        List<Integer>[] graph = new ArrayList[n];\n        for (int i = 0; i < n; i++) {\n            graph[i] = new ArrayList<>();\n        }\n\n        for (List<Integer> conn : connections) {\n            int n1 = conn.get(0);\n            int n2 = conn.get(1);\n            graph[n1].add(n2);\n            graph[n2].add(n1);\n        }\n\n        int[] disc = new int[n]; // discovery time of each node\n        int[] low = new int[n]; // earliest discovered node reachable from this node in DFS\n        boolean[] visited = new boolean[n]; // whether this node has been visited in DFS\n        List<List<Integer>> out = new ArrayList<>();\n\n        dfs(0, -1, disc, low, visited, graph, out); // arbitrarily pick a node to start DFS\n\n        return out;\n    }\n\n    // root = current node under consideration\n    // parent = parent of current node\n    private void dfs(int root, int parent, int[] disc, int[] low, boolean[] visited, List<Integer>[] graph, List<List<Integer>> out) {\n        visited[root] = true;\n        disc[root] = time++;\n        low[root] = disc[root]; // we don\'t have to initialize low[] to inf because of this line\n\n        for (Integer nei : graph[root]) {\n            if (nei == parent) {\n                continue;\n            }\n\n            if (!visited[nei]) {\n                dfs(nei, root, disc, low, visited, graph, out);\n                low[root] = Math.min(low[root], low[nei]);\n                if (disc[root] < low[nei]) {\n                    out.add(Arrays.asList(root, nei));\n                }\n            } else {\n                low[root] = Math.min(low[root], disc[nei]);\n            }\n        }\n    }\n}\n```\n\n\n**Complexity analysis of array-based implementation**\nE = total number of edges = connections.size()\nV = total number of vertices = n\n\n**time complexity: O(V + E)**\nExplanation: \nI build the graph explicitly. The 1st for-loop loops over each vertice, which costs O(V). The 2nd for-loop loops over each edge, which costs O(E). \nThen I perform DFS that visits each vertice and edge once, which costs O(V + E).\nTherefore, the total time complexity is O(V + E)\n\n**extra space complexity: O(V + E)**\nThe variable "graph" is an adjacency list representatoin of the grpah, which costs O(V + E) space.\nThe stack usage of DFS costs O(V + E) space in worst case (which occurs when the graph is a stick)\nTherefore, the total extra space complexity is O(V + E)\n
['Java']