# Java(just like meeting point problem)

• ``````public class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int i = 0, j = nums.length-1;
int count = 0;
while(i < j){
count += nums[j]-nums[i];
i++;
j--;
}
return count;
}
}``````

• Niiiiiiiiiiiiiiiiice!

• Need not to sort the entire array. Linear time QuickSelect is preferred here to compute median and solve this problem in O(n).

• Same idea:

``````public class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int res = 0, mid = nums.length/2;
for(int i = 0; i < nums.length; i++){
res += i > mid ? nums[i] - nums[mid] : nums[mid] - nums[i];
}
return res;
}
}
``````

• Could you please explain why the solution works?

• Wait why does this work? It seems just out of the blue.

• @lekzeey
@s961206
you can think the number in the array is the position in 1d array. so, we need to find a position that all positions can reach and the sum is minimum.
just like this problem in 1d
https://leetcode.com/problems/best-meeting-point/
Hope it helps

• @lekzeey @s961206
Suppose you have two endpoints A and B, when you want to find a point C that has minimum sum of distance between AC and BC, the point C will always between A and B. Draw a graph and you will understand it. Lets keep moving forward. After we locating the point C between A and B, we can define that
dis(AC) = c - a; dis(CB) = b - c;
sum = dis(AC) + dis(CB) = b - a.
b - a will be a constant value, given specific b and a. Thus there will be no difference between points among A and B.

In this problem, we set two boundaries, saying i and j, and we move the i and j to do the computation.

Hope it helps.

• The first time I actually used `quick select` to select the median element, which I thought would be faster than `Arrays.sort()` function. But it turned out that it's actually much slower than `quick sort` which is `.sort()` method. Anyone knows why?

``````Arrays.sort(nums);
int i = 0, j = nums.length - 1, res = 0;
while (i < j)
res += nums[j--] - nums[i++];
return res;
``````

• @zhugejunwei I think Python used Timsort not quick sort. Also the .sort() method in python is written in C which should be much faster than your quick select in Python. I guess this is the reason.

• Nice solution!
Similar one, via streams:

``````int minMoves2(int[] nums) {
Arrays.sort(nums);
int median = nums[nums.length >> 1];
return Arrays.stream(nums).map(i -> Math.abs(median - i)).sum();
}
``````

• @fatalme - Similar logic but different way

public int minMoves2(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int sum = 0;
Arrays.sort(nums);
for(int i : nums)
sum += Math.abs(i-nums[nums.length/2]); // distance of all from median
return sum;
}

• This post is deleted!

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