# Best Meeting Point

• One potential optimization for Solution #3: since we only care about the median value, we could use "find kth smallest element" to find the median of column in O(N).
C++ STL has nth_element which rearranges the elements in the range in such a way that the element at the nth position is the element that would be in that position in a sorted sequence. So the time complexity of Solution #3 would be O(mn) I think.
AC C++ code in the pic attached.

• Yup, you can use the famous selection algorithm to optimize Solution #3 to O(mn), but you don't have to. I mentioned that briefly in Solution #4.

• For #3, why we do not need to sort rows?

• @jonsnow1984 Because when you append elements in `rows`, it is already sorted. In other words, you are inserting the row index of every element. For example, you always insert 0's, then insert 1's in `rows`.

• O(mn) time O(m+n) space:

``````class Solution {
public int minTotalDistance(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
if (n == 0) {
return 0;
}

int k = 0;
int[] x = new int[m];
int[] y = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
x[i]++;
y[j]++;
k++;
}
}
}

int m_x = getMedium(x, k/2);
int m_y = getMedium(y, k/2);

return getDist(x, m_x) + getDist(y, m_y);
}

private int getMedium(int[] nums, int m) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum > m) {
return i;
}
}
return 0;
}

private int getDist(int[] nums, int m) {
int dist = 0;
for (int i = 0; i < nums.length; i++) {
dist += nums[i] * Math.abs(i - m);
}
return dist;
}
}
``````

• O(mn) time O(1) space:

``````class Solution {
public int minTotalDistance(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
if (n == 0) {
return 0;
}

int k = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
k++;
}
}
}

int count = 0;
int m_x = -1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
count++;
}
if (count > k / 2) {
m_x = i;
break;
}
}
if (m_x != -1) {
break;
}
}

count = 0;
int m_y = -1;
for (int j = 0; j < n; j++) {
for (int i = 0; i < m; i++) {
if (grid[i][j] == 1) {
count++;
}
if (count > k / 2) {
m_y = j;
break;
}
}
if (m_y != -1) {
break;
}
}

int dist = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
dist += Math.abs(i - m_x) + Math.abs(j - m_y);
}
}
}

return dist;
}
}
``````

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