instagram

Google Interview Algorithm Sort Given a 2D matrix of integers

by omt

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;
	}

}
Share