Java 2ms/Python 40ms two pointers solution no median no sort with explanation


  • 37

    Before solving the 2D problem we first consider a 1D case. The solution is quite simple. Just find the median of all the x coordinates and calculate the distance to the median.

    Alternatively, we can also use two pointers to solve the 1D problem. left and right are how many people one left/right side of coordinates i/j. If we have more people on the left we let j decrease otherwise increase i. The time complexity is O(n) and space is O(1).

    To be more clear, a better view is we can think i and j as two meet points. All the people in [0, i] go to meet at i and all the people in [j, n - 1] meet at j. We let left = sum(vec[:i+1]), right = sum(vec[j:]), which are the number of people at each meet point, and d is the total distance for the left people meet at i and right people meet at j.

    Our job is to let i == j with minimum d.

    If we increase i by 1, the distance will increase by left since there are 'left' people at i and they just move 1 step. The same applies to j, when decrease j by 1, the distance will increase by right. To make sure the total distance d is minimized we certainly want to move the point with less people. And to make sure we do not skip any possible meet point options we need to move one by one.

    For the 2D cases we first need to sum the columns and rows into two vectors and call the 1D algorithm.
    The answer is the sum of the two. The time is then O(mn) and extra space is O(m+n)

    Moreover, the solution is still O(mn) with the follow up:

    What if there are people sharing same home?
    In other words the number in the grid can be more than 1.

    Java

    public class Solution {
        public int minTotalDistance(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            int[] row_sum = new int[n], col_sum = new int[m];
    
            for (int i = 0; i < m; ++i)
                for (int j = 0; j < n; ++j) {
                    row_sum[j] += grid[i][j];
                    col_sum[i] += grid[i][j];
                }
    
            return minDistance1D(row_sum) + minDistance1D(col_sum);
        }
    
        public int minDistance1D(int[] vector) {
            int i = -1, j = vector.length;
            int d = 0, left = 0, right = 0;
    
            while (i != j) {
                if (left < right) {
                    d += left;
                    left += vector[++i];
                }
                else {
                    d += right;
                    right += vector[--j];
                }
            }
            return d;
        }
    
    }
    // Runtime: 2ms
    

    Python

    def minTotalDistance(self, grid):
        row_sum = map(sum, grid)
        col_sum = map(sum, zip(*grid)) # syntax sugar learned from stefan :-)
    
        def minTotalDistance1D(vec):
            i, j = -1, len(vec)
            d = left = right = 0
            while i != j:
                if left < right:
                    d += left
                    i += 1
                    left += vec[i]
                else:
                    d += right
                    j -= 1
                    right += vec[j]
            return d
    
        return minTotalDistance1D(row_sum) + minTotalDistance1D(col_sum)
    
    
    # 57 / 57 test cases passed.
    # Status: Accepted
    # Runtime: 40 ms

  • 0
    H

    "sl and sr are how many people one left/right side of coordinates l/r. If we have more people on the left we let r decrease otherwise increase l" why + - 1 for +- 2 or any other number?


  • 1

    Maybe I didn't phase it well. A better view is we can think l and r as two meet points. All the people in [0, l] go to meet at l and all the people in [r, n - 1] meet at r. We let sl = sum(vec[:l+1]), sr = sum(vec[r:]), which are the number of people at each meet point, and d is the total distance for the sl people meet at l and sr people meet at r.

    Our job is to let l == r with minimum d.

    If we increase l by 1, the distance will increase by sl since there are sl people at l and they just move 1 step.
    The same applies to r, when decrease r by 1, the distance will increase by sr.
    To make sure the total distance d is minimized we certainly want to move the point with less people. And to make sure we do not skip any possible meet point options we need to move one by one thus +- 1 not 2 or anything else.

    Is this clear enough?


  • 0
    A

    Inspired by your!

    def minTotalDistance(self, grid):
        row_sum = map(sum, grid)
        col_sum = [0] * len(grid[0])
        for i in xrange(len(grid[0])):
            for j in xrange(len(grid)):
                col_sum[i] += grid[j][i]
        
        return self.find_dis(row_sum) + self.find_dis(col_sum)
    
    def find_dis(self, vec):
        size = len(vec)
        left, right = -1, size
        count_l, count_r = 0, 0
        while left < right:
            if count_l < count_r:
                left += 1
                count_l += vec[left]
            else:
                right -= 1
                count_r += vec[right]
    
        # median is right (left)
        dis = 0
        for i in xrange(size):
            dis += vec[i]*abs(i-left)
        return dis

  • 0
    Y
    This post is deleted!

  • 0
    F

    I think your two pointer method is correct, but the explanation is a little ambiguous, it is like Greedy idea, always choose small value to forward/backward. I think this problem can be converted to Elevator schedule problem which wants find out which floor the elevator stops can make the total steps people need to take to their floor minimum.

    let A[i] is the total steps if elevator stop ith floor, then there are following transition equation:
    A[i] = A[i-1] + sum[0,i-1]-sum[i,n-1], we need to find the flecxion point for sum[0,i-1]-sum[i,n-1], i is in [0,n-1]. This flecxion point is the floor or meeting point.
    By this idea, I give following O(n) solution for finding meeting point.

    	// the simple case to get the median number for every floor has 1 person at most.
        private int minMoves1D(int[] nums) {
        	int sum = 0;
        	for (int num: nums) sum += num;
        	if (sum == 0) return 0;
        	int pos = 0, cur = 0;
        	while (pos < nums.length && cur < sum) {
        		cur += nums[pos];
        		sum -= nums[pos];
        		pos++;
        	}
        	pos--;
        	int res = 0;
        	for (int i = 0; i < nums.length; i++) res += nums[i]*Math.abs(pos-i);
        	return res;
        }

  • 0
    L

    @dietpepsi Here in minTotalDistance1D function, why is i and j initialized to -1 and vector.length. If I initialize it to 0 and vector.length -1 and do left += vector[i++] (same for right) instead, I get wrong answer. Did not understand why. Btw very nice solution


Log in to reply
 

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