Map Of Highest Peak - Easy Solution and Nice Explanation 💯🤩
Intuition

Top-left to Bottom-right traversal ensures that the right height is updated in the heights matrix.


Further reverse traversal from Bottom-right to T
# Intuition
1. Top-left to Bottom-right traversal ensures that the right height is updated in the heights matrix.

1. Further reverse traversal from Bottom-right to Top-left ensures that the mapped height is correct and it tries to still minimize the heights.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach

**Initialization**:

Initialize m to be the number of rows in the matrix isWater and n to be the number of columns in the matrix isWater.

    int m=isWater.length;
    int n=isWater[0].length;

Initialize the matrix heights with the size of m and n.

    int[][] heights=new int[m][n];

Initialize maxVal to be some random maximum value of 2000 for further processing with that.

    int maxVal=2000;

**Initial updation of heights**:

Traverse each cell in the matrix isWater by iterating the outer loop from 0 to m and iterating the inner loop from 0 to n.

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){

Check if isWater at the index i and j is equal to 1(this is water area),hence update heights to be 0 at that index.

    if(isWater[i][j]==1)
    {
        heights[i][j]=0;
    }

Otherwise,update the heights with the value 1 for further processing.

    else
    {
        heights[i][j]=1;
    }

**Top-left to Bottom-right traversal**:

Traverse each cell in the matrix isWater by iterating the outer loop from 0 to m and iterating the inner loop from 0 to n.

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){

Check if the heights at the index i and j is not equal to 0,If so it needs to be updated.

    if(heights[i][j]!=0){

Hence first fix the top and left value to be maxVal.

    int topVal=maxVal;
    int leftVal=maxVal;

Check if we can traverse top by checking if i-1>=0 -> if so,update topVal to be the heights[i-1][j].

    if(i-1>=0)
    {
        topVal=heights[i-1][j];
    }

Check if we can traverse left by checking if j-1>=0 -> if so,update leftVal to be the heights[i][j-1].

    if(j-1>=0)
    {
        leftVal=heights[i][j-1];
    }

Update the current height with minimum of the topVal and leftVal plus 1.

    heights[i][j]=Math.min(topVal,leftVal)+1;

**Bottom-right to Top-left Traversal**:

Iterate through all the elements of the matrix isWater in reverse order starting from m-1 to 0 and n-1 to 0.This is for the purpose to minimize the heights further.

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){

Check if the heights at the index i and j is not equal to 0,If so it needs to be updated.

    if(heights[i][j]!=0){

Hence first fix the bottom and right value to be maxVal.

    int bottomVal=maxVal;
    int rightVal=maxVal;

Check if we can traverse bottom by checking if i+1 < m  -> if so,update bottomVal to be the heights[i+1][j].

    if(i+1<m)
    {
        bottomVal=heights[i+1][j];
    }

Check if we can traverse right by checking if j+1 < n -> if so,update rightVal to be the heights[i][j+1].

    if(j+1<n)
    {
        rightVal=heights[i][j+1];
    }

Update the current height with minimum of the topVal and leftVal plus 1 and current value updated in the former loop.

    heights[i][j]=Math.min(heights[i][j],Math.min(bottomVal,rightVal)+1);

**Returning the result**:

Return heights matrix of size mxn which contains the heights at each cell.

    return heights;

<!-- Describe your approach to solving the problem. -->

# Complexity
- ***Time complexity***: **O(mxn)**.
   m -> number of rows in the matrix isWater.
   n -> number of columns in the matrix isWater.

**First loop for initial updation**: **O(mxn)**.

First loop for initial updation of the heights matrix traverse through every element of the matrix isWater.Hence it takes **O(mxn) time complexity**.

**Second loop for Top-left to Bottom-right Traversal**: **O(mxn)**.

Next loop is used to traverse over all the cells in isWater matrix from **top-left to bottom-right**.Hence it takes **O(mxn) time**.

**Third loop for Bottom-right to Top-left Traversal**: **O(mxn)**.

Next loop is used to traverse over all the cells in **reverse manner from Bottom-right to Top-left**.Hence it takes **O(mxn) time**.

**Total Time Complexity**: **O(mxn)**.

Total Time Complexity is contributed by all the three loops **O(mxn)+O(mxn)+O(mxn) = O(mxn) time** in total.
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- ***Space complexity***: **O(1)**.

In-place updates, so **O(1) extra space** .

Some variables like m,n,maxVal,topVal,bottomVal,rightVal,leftVal consumes only **constant space**.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public int[][] highestPeak(int[][] isWater) {
        //size mxn : map of land and water cells
        // 0 : land cell     1 : water cell

        //assign height by
        //height of each cell : non-negative
        //water cell : height 0
        //Two adjacent cells : height difference atmost 1

        //assignment of heights : max height is maximized
    int m=isWater.length;
    int n=isWater[0].length;

    int[][] heights=new int[m][n];
    //random max value
    int maxVal=2000;

    //Initial updation of heights matrix
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
           if(isWater[i][j]==1)
           {
            heights[i][j]=0;
           }
           else
           {
            heights[i][j]=1;
           }
        }
    }

    //Top-left to bottom-right traversal
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(heights[i][j]!=0)
            {

            
            int topVal=maxVal;
            int leftVal=maxVal;

            if(i-1>=0)
            {
                topVal=heights[i-1][j];
            }
            if(j-1>=0)
            {
                leftVal=heights[i][j-1];
            }
            heights[i][j]=Math.min(topVal,leftVal)+1;
            }
        }
    }

    //bottom-right to top-left traversal
    for(int i=m-1;i>=0;i--)
    {
        for(int j=n-1;j>=0;j--)
        {
            if(heights[i][j]!=0)
            {
                int bottomVal=maxVal;
                int rightVal=maxVal;

                if(i+1<m)
                {
                    bottomVal=heights[i+1][j];
                }
                if(j+1<n)
                {
                    rightVal=heights[i][j+1];
                }
                heights[i][j]=Math.min(heights[i][j],Math.min(bottomVal,rightVal)+1);
            }
        }
    }
    return heights;

     }
}

```
['Array', 'Matrix', 'Java']