Java solution, slow but clear. Coursera Princeton algorithms course
I am using Coursera algorithms (Princeton, Robert Sedgewick) course ideas so code should be easy to understand if you watched it.\nIdea is based on building a G
I am using Coursera algorithms (Princeton, Robert Sedgewick) course ideas so code should be easy to understand if you watched it.\nIdea is based on building a Graph from the matrix using adjucencyMap representation and then use BFS to fins path from shortest tree to next shortest tree in this graph:\nStep 1a: build adjucency HashMap (graph) of cells we can visit\nStep 1b: build TreeMap (treeHeight, index) in order to know which trees to visit first \nStep 2: run BFS to find distance from start to shortestTree; start = shortestTreeIndex after\nStep 3: visit and cut trees in order from shortest one, if tree cannot be reached -> return -1\n\n**Note: this solution is extremely slow (bottom 5% on speed and memory by leetcode mertics)**\n\nIt supposed to be:\n```\nM == forest.length\nN == forest[i].length\nO(MN) -> building adjucency Map\nO(MN)*log(MN) -> building heightIndexMap (TreeMap)\nO(MN * (MN + 4MN)) -> running BFS to find shortest pathts between shortest and nextShortest tree.\nTime complexity of BFS is O(V + E) when Adjacency List is used.\nFor each tree we can have maximum of 4*MN edges and we are running BFS MN times, so it totales to O(MN * (MN + 4MN))\n```\nTme complexity is sum of the above, which can be simplified to O(MN * (MN + 4MN)) = O((MN)^2)\n\n**Bonus: the solution should work if input is not a matrix, but a `List<List<Integer>> forest` with random number of cells in each row**\n\n\n```\nclass Solution {\n    Map<Integer, List<Integer>> adjucencyMap;\n    Map<Integer, Integer> heightIndexMap;\n    int forestSize = 0;\n    \n    public int cutOffTree(List<List<Integer>> forest) {\n        if(forest.get(0).get(0) == 0){\n            //(0,0) point is blocked\n            return -1;\n        }\n        \n        adjucencyMap = new HashMap<>();        \n        //we use TreeMap so that trees will be sorted by height\n        heightIndexMap = new TreeMap<>();\n        forestSize = 0;\n        \n        for(int i = 0; i<forest.size(); i++){\n            for(int j = 0; j<forest.get(i).size(); j++){    \n                int cell = forest.get(i).get(j);\n                int index = i*forest.get(i).size() + j + 1;\n                //only consider trees we need to cut, ignore "1\'s"\n                if(cell > 1){\n                    heightIndexMap.put(forest.get(i).get(j), index);\n                }\n                \n                //only consider walkable cells\n                if(cell > 0) {\n                    List<Integer> adjucent = new ArrayList<>();\n                    if(j-1 >= 0 && forest.get(i).get(j-1) > 0){\n                        //add left\n                        adjucent.add(index - 1);  \n                    }\n                    if(j+1 < forest.get(i).size() && forest.get(i).get(j+1) > 0){\n                        //add right\n                        adjucent.add(index + 1);  \n                    }\n                    if(i-1 >= 0 && j < forest.get(i-1).size() && forest.get(i-1).get(j) > 0){\n                       //add top\n                        adjucent.add(index - forest.get(i-1).size()); \n                        \n                    }\n                    if(i+1 < forest.size() && j < forest.get(i+1).size() && forest.get(i+1).get(j) > 0){\n                        //add bot\n                        adjucent.add(index + forest.get(i).size()); \n                    }               \n                    adjucencyMap.put(index, adjucent);                        \n                }\n                \n                forestSize++;\n            }\n        }\n        \n        int result = 0;\n        int startIndex = 1;\n        List<Integer> sortedTrees = new ArrayList(heightIndexMap.keySet());\n        \n        for(int i = 0; i < sortedTrees.size(); i++){\n            int height = sortedTrees.get(i);\n            int targetIndex = heightIndexMap.get(height);\n            int dist = bfsFindDist(startIndex, targetIndex);\n            if(dist == -1){\n                return dist;\n            }\n            result += dist;\n            startIndex = targetIndex;\n        }\n        \n       return result;\n    }\n    \n    // return: distance from startTreeIndex to targetTreeIndex\n    // -1 if no path found\n    int bfsFindDist(int startTreeIndex, int targetTreeIndex){\n        if(startTreeIndex == targetTreeIndex){\n            return 0;\n        }\n        \n        List<Integer> distances = new ArrayList<>();\n        for(int i = 0; i<=forestSize; i++){\n            distances.add(i, -1);\n        }\n        \n        List<Boolean> visited = new ArrayList<>();\n        for(int i = 0; i<=forestSize; i++){\n            visited.add(i, false);\n        }\n        \n        visited.set(startTreeIndex, true);\n        distances.set(startTreeIndex, 0);      \n        Queue<Integer> queue = new LinkedList<>();\n        queue.add(startTreeIndex);\n        while(!queue.isEmpty()){\n            int tree = queue.remove();\n            for(int adj : adjucencyMap.get(tree)){\n                if(adj == targetTreeIndex){\n                    return distances.get(tree)+1;\n                }\n                if(!visited.get(adj)){\n                    queue.add(adj);\n                    visited.set(adj, true);\n                    distances.set(adj, distances.get(tree)+1);\n                }\n            }\n        }\n        \n        return distances.get(targetTreeIndex);\n    }\n}\n```
[]