Google Interview Algorithm Sort Given a 2D matrix of integers
Given a 2D matrix of integers, sort it such that:
- every row is sorted in ascending order from left to right
- every column is sorted in ascending order from top to down
- all items in the same row are unique
You may assume the input matrix is always valid, meaning that such a sort is always possible.
For example:
for input matrix
1 3 5
3 2 4
the output could be any of the following:
valid output #1:
1 3 4
2 3 5
valid output #2:
1 2 3
3 4 5
valid output #3:
1 3 4
2 3 5
One kinda trivial solution is to sort the 2D matrix column wise.
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class SortingMatrix { public static void main(String[] args) { // int array[][] = { { 1, 3, 5 }, { 3, 2, 4 } }; // int array[][] = { { 12, 33, 54 }, { 23, 27, 14 } }; int array[][] = { { 1, 2, 3 }, { 3, 4, 5 } }; array = sort2DMatrix(array); for (int[] i : array) { for (int a : i) { System.out.print(a + " "); } System.out.println(); } } public static int[][] sort2DMatrix(int[][] array) { List<Integer> list = new ArrayList<>(); int totalNumberOfArrays = array.length; for (int count = 0; count < totalNumberOfArrays; count++) { for (int index = 0; index < array[count].length; index++) { list.add(array[count][index]); } } Collections.sort(list); int[][] result = new int[2][list.size() / 2]; int currentCount = 0; for (int count = 0; count < list.size();) { result[0][currentCount] = list.get(count++); result[1][currentCount++] = list.get(count++); } return result; } }