296. Best Meeting Point (Hard) - TengnanYao/daily_leetcode GitHub Wiki

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minTotalDistance = function(grid) {
    // math solution, median
    const [m, n] = [grid.length, grid[0].length]
    let xs = [], ys = []
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                xs.push(i)
                ys.push(j)
            }
        }
    }
    xs.sort((a, b) => {return a - b})
    ys.sort((a, b) => {return a - b})
    const len = xs.length
    const [x, y] = [xs[parseInt(len / 2)], ys[parseInt(len / 2)]]
    let result = 0
    for (let i = 0; i < len; i++) {
        result += Math.abs(xs[i] - x + ys[i] - y)
    }
    return result
    
    // // dp solution
    // const dp = []
    // const nums = []
    // const [m, n] = [grid.length, grid[0].length]
    // for (let i = 0; i < m; i++) {
    //     let temp = [], ltr = [], rtl = []
    //     let num = 0, cur = 0
    //     let count = 0
    //     for (let j = n - 1; j >= 0; j--) {
    //         cur += num
    //         rtl.unshift(cur)
    //         if (grid[i][j] === 1) {
    //             num++
    //             count++
    //         }
    //     }
    //     nums.push(count)
    //     num = 0, cur = 0
    //     for (let j = 0; j < n; j++) {
    //         cur += num
    //         ltr.push(cur)
    //         temp.push(cur + rtl[j])
    //         if (grid[i][j] === 1) {
    //             num++
    //         }
    //     }
    //     dp.push(temp)
    // }
    // let ttb = [], btt = []
    // let count = 0
    // for (let i = m - 1; i >= 0; i--) {
    //     let temp = []
    //     for (let j = 0; j < n; j++) {
    //         if (i === m - 1) {
    //             temp.push(0)
    //         } else {
    //             temp.push(btt[0][j] + dp[i + 1][j] + count)
    //         }
    //     }
    //     count += nums[i]
    //     btt.unshift(temp)
    // }
    // count = 0
    // let result = Infinity
    // for (let i = 0; i < m; i++) {
    //     let temp = []
    //     for (let j = 0; j < n; j++) {
    //         if (i === 0) {
    //             temp.push(0)
    //         } else {
    //             temp.push(ttb[ttb.length - 1][j] + dp[i - 1][j] + count)
    //         }
    //         result = Math.min(temp[j] + btt[i][j] + dp[i][j], result)
    //     }
    //     count += nums[i]
    //     ttb.push(temp)
    // }
    // return result
};