2ms Median Point and 8ms DP Implementation


  • 1
    O

    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;
        }
    }

Log in to reply
 

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