LeetCode 1765: Map of Highest Peak Solution

Master LeetCode problem 1765 (Map of Highest Peak), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1765. Map of Highest Peak

Medium

Array Breadth-First Search Matrix

Problem Explanation

Explanation

To solve this problem, we can use a breadth-first search (BFS) approach starting from all water cells. We initialize a queue with all water cells and assign them a height of 0. Then, we traverse the cells in the queue and assign heights to their neighboring land cells based on the water cells' heights. We continue this process until all cells have been visited.

By assigning heights based on the water cells, we ensure that the height difference between adjacent cells is at most 1. This way, we can maximize the overall height in the matrix.

Algorithm:

Initialize a queue and add all water cells to the queue with a height of 0.
Perform a BFS traversal on the matrix:
- For each cell in the queue:
  - Pop the cell from the queue.
  - Explore its neighbors:
    - If the neighbor is a valid land cell and has not been visited yet, assign it a height based on the current cell's height.
    - Add the neighbor to the queue.
Return the resulting height matrix.

Time Complexity:

The time complexity of this approach is O(m * n), where m is the number of rows and n is the number of columns in the matrix.

Space Complexity:

The space complexity is also O(m * n) to store the queue and the resulting height matrix.

Solution Code

class Solution {
    public int[][] highestPeak(int[][] isWater) {
        int m = isWater.length;
        int n = isWater[0].length;
        int[][] height = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        
        for (int i = 0; i < m; i++) {
            Arrays.fill(height[i], -1);
            for (int j = 0; j < n; j++) {
                if (isWater[i][j] == 1) {
                    height[i][j] = 0;
                    queue.offer(new int[]{i, j});
                }
            }
        }
        
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0];
            int y = curr[1];
            for (int[] dir : dirs) {
                int newX = x + dir[0];
                int newY = y + dir[1];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && height[newX][newY] == -1) {
                    height[newX][newY] = height[x][y] + 1;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }
        
        return height;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1765 (Map of Highest Peak)?

This page provides optimized solutions for LeetCode problem 1765 (Map of Highest Peak) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1765 (Map of Highest Peak)?

The time complexity for LeetCode 1765 (Map of Highest Peak) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1765 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1765 in Java, C++, or Python.

Back to LeetCode Solutions