[Java/Python 3] 2 BFS codes w/ brief explanation and analysis.
Q & A\nQ1: Why are we trying to find the shortest path? \nA1: We are not looking for shortest path, just following the rules of the problems to maximize the hei
**Q & A**\nQ1: Why are we trying to find the shortest path? \nA1: We are not looking for shortest path, just following the rules of the problems to maximize the heights of all cells;\n\nQ2: Why do we use BFS here? Why does it even work? Why does BFS guarantee the maximum height?\nA2: \na. According to the problem requirement, we need to assign the value of 0 to all waters; \nb. all lands neighboring waters have a value at most 1;\nc. all lands neighboring lands with a value of 1 will have a value at most 2; \nd. all lands neighboring lands with a value of 2 will have a value at most 3;\n...\nThe problem requires that all neighboring cells height difference is at most 1.\n\nFrom waters we start to BFS, in each step we maximize the difference between the neighboring cells as `1`.  Therefore we can guarantee the maximum height.\n**End of Q & A**\n\n----\n\n1. Since the height of all waters is 0, we start from waters with a height of 0;\n2. The difference of all adjacent cells heights is at most 1, according to the rule of the problem; Therefore, we can use BFS to assign heights to neighboring cells by increasing height by 1.\n \n**Method 1:** -- credit to **@celticrocks** for suggestion to remove HashSet.\n\n\n```java\n    private static final int[] d = {0, 1, 0, -1, 0};\n    public int[][] highestPeak(int[][] A) {\n        int m = A.length, n = A[0].length;\n        Queue<int[]> q = new LinkedList<>();\n        for (int r = 0; r < m; ++r) {\n            for (int c = 0; c < n; ++c) {\n                if (A[r][c] == 1) {\n                    q.offer(new int[]{r, c}); // put its position into Queue as one of the starting points of BFS.\n                }\n                --A[r][c]; // Set the height to 0, the land by -1.\n            }\n        }\n        while (!q.isEmpty()) { // BFS starts here.\n            int[] pos = q.poll(); // Current position.\n            int r = pos[0], c = pos[1];\n            for (int k = 0; k < 4; ++k) { // Traverse its neighbors.\n                int x = r + d[k], y = c + d[k + 1];\n                if (0 <= x && x < m && 0 <= y && y < n && A[x][y] < 0) {\n                    A[x][y] = A[r][c] + 1; // assign corresponding height value.\n                    q.offer(new int[]{x, y}); // put its position into Queue for next round of BFS.\n                }            \n            }\n        }\n        return A;\n    }\n```\n```python\n    def highestPeak(self, A: List[List[int]]) -> List[List[int]]:\n        dq, height = deque(), 0\n        for r, row in enumerate(A):\n            for c, cell in enumerate(row):\n                if cell == 1:\n                    A[r][c] = 0\n                    dq.append((r, c))\n                else:\n                    A[r][c] = -1    \n        while dq:\n            r, c = dq.popleft()\n            for x, y in (r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c):\n                if len(A) > x >= 0 <= y < len(A[0]) and A[x][y] < 0:\n                    A[x][y] = A[r][c] + 1\n                    dq.append((x, y))\n        return A\n```\n\n----\n\n\n**Method 2:**\nIn case you need a version without modifying input array, here it is:\n\n```java\n    private static final int[] d = {0, 1, 0, -1, 0};\n    public int[][] highestPeak(int[][] A) {\n        int m = A.length, n = A[0].length;\n        int[][] heights = new int[m][n];\n        Queue<int[]> q = new LinkedList<>();\n        for (int r = 0; r < m; ++r) {\n            for (int c = 0; c < n; ++c) {\n                if (A[r][c] == 1) { // Water found.\n                    heights[r][c] = 0; // Set the height to 0.\n                    q.offer(new int[]{r, c}); // put its position into Queue as one of the starting points of BFS.\n                }else {\n                    heights[r][c] = -1; // Mark the land by -1.\n                }\n            }\n        }\n        while (!q.isEmpty()) {\n            int[] pos = q.poll(); // Current position.\n            int r = pos[0], c = pos[1];\n            for (int k = 0; k < 4; ++k) { // Traverse its neighbors.\n                int x = r + d[k], y = c + d[k + 1];\n                if (0 <= x && x < m && 0 <= y && y < n && heights[x][y] < 0) { // Found a neighbor land.\n                    heights[x][y] = heights[r][c] + 1; // Its neighbor height value is at most 1 bigger.\n                    q.offer(new int[]{x, y}); // put its position into Queue for next round of BFS.\n                }            \n            }\n        }\n        return heights;\n    }\n```\n\n```python\n    def highestPeak(self, A: List[List[int]]) -> List[List[int]]:\n        m, n = map(len, (A, A[0]))\n        dq, heights = deque(), [[-1] * n for _ in range(m)]\n        for r, row in enumerate(A):\n            for c, cell in enumerate(row):\n                if cell == 1:\n                    heights[r][c] = 0\n                    dq.append((r, c))\n        while dq:\n            for _ in range(len(dq)):\n                r, c = dq.popleft()\n                for x, y in (r, c + 1), (r, c - 1), (r + 1, c), (r - 1, c):\n                    if m > x >= 0 <= y < n and heights[x][y] < 0:\n                        heights[x][y] = heights[r][c] + 1\n                        dq.append((x, y))\n        return heights\n```\n**Analysis:**\n\nTime & space: O(m * n).
[]