zhtt2009
BAN USER- 1of 1 vote
AnswersGiven 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 matrix1 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. For example, you can push all items into a heap and pop one after another, putting it into the matrix column after column. This would be a `O(n lg n)` time complexity where `n` is the number of items in the matrix, i.e., `n = rows*cols`. Can you design a more efficient algorithm?
- zhtt2009 in United States
Follow-up: What if all items in the same column are also required to be unique?| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm
RepI am Frank, 29 year old. I have worked with numerous branches, including payroll and human resources, which allows me ...
Repcassicjohnson, Android Engineer at Accenture
Hi, I work as an Painter, making art Paintings for the world’s top art galleries. When I have an ...