> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/kth-manhattan-distance-neighbourhood.md).

# Kth Manhattan Distance Neighbourhood

Given a matrix M of size nxm and an integer K, find the maximum element in the K manhattan distance neighbourhood for all elements in nxm matrix.\
In other words, for every element M\[i]\[j] find the maximum element M\[p]\[q] such that `abs(i-p)+abs(j-q) <= K`.

`Note: Expected time complexity is O(N*N*K)`

**Constraints:**

```
1 <= n <= 300
1 <= m <= 300
1 <= K <= 300
0 <= M[i][j] <= 1000
```

**Example:**

```
Input:
M  = [[1,2,4],[4,5,8]] , K = 2

Output:
ans = [[5,8,8],[8,8,8]]
```

```java
public class Solution {
    public int[][] solve(int K, int[][] matrix) {
        int n = matrix.length, m = matrix[0].length, min = Integer.MIN_VALUE;
        int[][][] dp = new int[K + 1][n][m];
        for (int k = 0; k <= K; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (k == 0)
                        dp[k][i][j] = matrix[i][j];
                    else {
                        int cur = min;
                        if (i > 0)
                            cur = Math.max(cur, dp[k - 1][i - 1][j]);
                        if (j > 0)
                            cur = Math.max(cur, dp[k - 1][i][j - 1]);
                        if (i < n - 1)
                            cur = Math.max(cur, dp[k - 1][i + 1][j]);
                        if (j < m - 1)
                            cur = Math.max(cur, dp[k - 1][i][j + 1]);
                        dp[k][i][j] = Math.max(cur, dp[k - 1][i][j]);
                    }
                }
            }
        }
        int[][] ans = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                ans[i][j] = dp[K][i][j];
        return ans;
    }
}
```