Java - ArrayList+BFS | NO TLE [with clear explanation and comments]
Complexities\n- Time Complexity: O(N^2 * M^2)\n- Space Complexity: O (N * M)\n\nThinking Process\n1. All trees shall be cut in the order of height -> we shall c
**Complexities**\n- Time Complexity: O(N^2 * M^2)\n- Space Complexity: O (N * M)\n\n**Thinking Process**\n1. All trees shall be cut in the order of height -> we shall create a list to store all of their heights and sort the list after all trees have been found\n2. Find the total steps need to cut all trees \n\t- Traverse through all tree -> traverse the list from index 0 (the tree with the smallest height)\n\t- Move to the next tree to cut -> use BFS to find the shortest path from current location to it\n\t(If a tree is unreacheable, then return -1)\n\n\n**PS**: \n1. *Why use ArrayList instead of PriorityQueue*? \n\tWe only need the **final** list to be sorted. If we were using PQ, then every insertion/deletion would need O(logK) time (K == size of PQ), making the process of adding all trees with a time complexity O(K log K) and polling all trees from the PQ with O(K log K). In comparison, ArrayList would only need to be sorted after all trees have been added, which having a time complexity of O(K log K) [< O(2K logK) if using PQ].\n\n\nPlease let me know if there\'s any mistakes. Thanks in advance.\n\n```\nclass Solution {\n    static int[] dy = {-1, 0, 1, 0};\n    static int[] dx = {0, 1, 0, -1};\n    \n    public int cutOffTree(List<List<Integer>> forest) {\n        int n = forest.size(), m = forest.get(0).size();\n        int count = 0;\n        \n\t\t// Store the height of all trees in a list\n        List<Integer> minList = new ArrayList<>();\n        for (List<Integer> al: forest)\n            for (int val: al) \n                if (val > 1) \n                    minList.add(val);\n        \n\t\t// Sort the list to have the smallest in the front\n        Collections.sort(minList);\n\t\t\n        int totalSteps = 0;\n        int si = 0, sj = 0; // Starting points <i, j>\n        \n        for (int i = 0; i < minList.size(); i++) {\n            int target = minList.get(i);\n            boolean hasFound = false;\n            boolean[][] visited = new boolean[n][m];\n\t\t\t\n            Queue<int[]> q = new LinkedList<>();\n            q.offer(new int[]{si, sj});\n        \n            int steps = -1;\n            while (!q.isEmpty() && !hasFound) {\n                steps++; // Increment the steps for current move\n\t\t\t\t\n\t\t\t\t// Level-Order Traversal\n\t\t\t\tint size = q.size();\n                while (size -- > 0) {\n                    int[] curr = q.poll();\n\t\t\t\t\t\n                    if (visited[curr[0]][curr[1]]) continue;\n                    visited[curr[0]][curr[1]] = true;\n                    \n\t\t\t\t\t// Skip if 0 is encountered\n                    if (forest.get(curr[0]).get(curr[1]) == 0) continue;\n                    \n\t\t\t\t\tif (forest.get(curr[0]).get(curr[1]) == target) {\n                        si = curr[0];\n                        sj = curr[1];\n                        hasFound = true;\n                        break;\n                    }\n\n\t\t\t\t\t// Typical BFS process\n                    for (int j = 0; j < dy.length; j++) {\n                        int y = curr[0] + dy[j];\n                        int x = curr[1] + dx[j];\n\t\t\t\t\t\t\n                        if (y >= n || x >= m || y < 0 || x < 0 || visited[y][x] || forest.get(y).get(x) == 0)   \n                            continue;\n                        q.offer(new int[]{y, x});\n                    }\n                }\n            }\n\t\t\t// If the target is unreacheable, end the entire process\n            if (steps == -1 || !hasFound) return -1;\n\n\t\t\ttotalSteps += steps;\n        }\n        return totalSteps;\n    }\n}\n```
['Breadth-First Search', 'Java']