LintCode 912 · Best Meeting Point.java

	// Approach #1 - T O(n * m) + O(p) + O(p log p), with p being # of 1 points.
	public class Solution {
	/**
	* @param grid: a 2D grid
	* @return: the minimize travel distance
	*/
	public int minTotalDistance(int[][] grid) {
	// handle corner cases
	if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
	return 0;
	}
	// step #0 scan the grid (n * m). And fill the lists.
	List<Integer> listX = new LinkedList<>();
	List<Integer> listY = new LinkedList<>();
	int n = grid.length, m = grid[0].length;
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
	if (grid[i][j] == 1) {
	listX.add(i);
	listY.add(j);
	}
	}
	}
	// get the ManhattanDistances and sum them up.
	int minTotal = 0;
	minTotal += getMinimumManhattanDistance(listX);
	// System.out.println(minTotal);
	Collections.sort(listY);
	minTotal += getMinimumManhattanDistance(listY);
	// System.out.println(minTotal);
	return minTotal;
	}
	private int getMinimumManhattanDistance(List<Integer> list) {
	int sum = 0;
	int begin = 0, end = list.size() - 1;
	while (begin < end) {
	sum += list.get(end) - list.get(begin);
	begin++;
	end--;
	}
	return sum;
	}
	}
	// Approach #2 - T O(n * m) + O(p) + O(p log p), with p being # of 1 points.
	// public class Solution {
	// /**
	// * @param grid: a 2D grid
	// * @return: the minimize travel distance
	// */
	// public int minTotalDistance(int[][] grid) {
	// // handle corner cases
	// if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
	// return 0;
	// }
	// // step #0 scan the grid (n * m).
	// List<Integer> listX = new LinkedList<>();
	// List<Integer> listY = new LinkedList<>();
	// for (int i = 0; i < grid.length; i++) {
	// for (int j = 0; j < grid[0].length; j++) {
	// if (grid[i][j] == 1) {
	// listX.add(i);
	// listY.add(j);
	// }
	// }
	// }
	// // step #1 find horizontal Median. O(n log n)
	// int minTotal = 0;
	// minTotal += getManhattanDistance(listX);
	// // step #2 find vertical Median. O(n log n)
	// Collections.sort(listY);
	// minTotal += getManhattanDistance(listY);
	// return minTotal;
	// }
	// private int getManhattanDistance(List<Integer> list) {
	// int sum = 0;
	// int median = getMedian(list);
	// for (int x : list) {
	// sum += Math.abs(x - median);
	// }
	// return sum;
	// }
	// private int getMedian(List<Integer> list) {
	// int size = list.size();
	// if (size % 2 == 1) {
	// return list.get(size / 2);
	// } else {
	// return (list.get(size / 2 - 1) + list.get(size / 2)) / 2;
	// }
	// }
	// }

view raw LintCode 912 · Best Meeting Point.java hosted with ❤ by GitHub