# 2ms Median Point and 8ms DP Implementation

• Sol. 1 Median Point Reference is in

https://leetcode.com/articles/best-meeting-point/#approach-3-sorting-accepted

Sol. 2 DP Solution is explained in the code

``````public class Solution {

///////////Sol. 1 Median Point ////////////    2ms

public int minTotalDistance(int[][] g) {
int n = g.length, m = g[0].length, nc = 0, nr = 0;
int[] col = new int[n * m], row = new int[n * m];

for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (g[i][j] > 0) col[nc++] = i;

for (int j = 0; j < m; j++)
for (int i = 0; i < n; i++)
if (g[i][j] > 0) row[nr++] = j;

return minD(col, nc) + minD(row, nr);
}

private int minD(int[] d, int n) {
int ans = 0;
for (int i = 0, j = n - 1; i < j; i++, j--) ans += d[j] - d[i];
return ans;
}

/////////Sol. 2 DP/////////////////////   8ms
// by points I mean people
// up[i][j] = min cost of all the points higher and equally high as i to go to i,j
// dn[i][j] = min cost of all the points lower and equally high as i to go to i,j
// left[i][j] = min cost of all the points on left of j on row i to go to i, j
// right[i][j] = min cost of all the points on right of j on row i to go to i, j
// upCnt[i] = number of points higher than i,j, including points on row i
// dnCnt[i] = number of points lower than i,j, including points on row i
// so the overall min cost ans =
// min{up[i-1][j]+upCnt[i-1]    +     dn[i + 1][j]+dnCnt[i+1]     +      left[i][j]+right[i][j]}, for all i,j
// or
// min{up[i - 1][j] + upCnt[i - 1] + dn[i][j]}, for all i,j

public int minTotalDistance_Sol2(int[][] grid) {
int n = grid.length, m = grid[0].length, cnt, j;
int[] row = new int[n + 2], upCnt = new int[n + 2], dnCnt = new int[n + 2];
int[][] left = new int[n + 2][m + 2], right = new int[n + 2][m + 2],
up = new int[n + 2][m + 2], dn = new int[n + 2][m + 2];

for (int i = 1; i <= n; i++) {
for (j = 1, cnt = 0; j <= m; cnt += grid[i - 1][j - 1], j++)
left[i][j] = left[i][j - 1] + cnt;
for (j = m, cnt = 0; j >= 1; cnt += grid[i - 1][j - 1], j--)
right[i][j] = right[i][j + 1] + cnt;
row[i] = cnt;
}
for (int i = 1, k = n; i <= n; i++, k--){
upCnt[i] = upCnt[i - 1] + row[i];
dnCnt[k] = dnCnt[k + 1] + row[k];
for (j = 1; j <= m; j++) {
up[i][j] = up[i - 1][j] + upCnt[i - 1] + left[i][j] + right[i][j];
dn[k][j] = dn[k + 1][j] + dnCnt[k + 1] + left[k][j] + right[k][j];
}
}

int ans = Integer.MAX_VALUE;
for (int i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
ans = Math.min(ans, up[i - 1][j] + upCnt[i - 1] + dn[i][j]);
return ans;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.