I need to insert into a sorted 2-D n x n matrix, insertion should be achieved in O(n). but the condition is the whole matrix is not sorted, only rows and columns are sorted.
example:
9 10 12 14
11 12 14 15
21 22 28 Null
23 24 Null Null
after inserting a new element into the above matrix the matrix should be sorted in row and column wise.
My approach
I am thinking to do something like inserting the new element at the end of the matrix (3, 3), from there I will check (3, 3-1) and (3-1, 3) I will swap (3, 3) with max[(3, 3-1), (3-1, 3)] if (3, 3) < max[(3, 3-1), (3-1, 3)], like that I will traverse the whole matrix until there is no swapping is required.
Please let me know If there is a better way to do it.