@Lucifer, I was thinking in the similar lines, but, I couldn't get the exact way of re-arranging the sub-matrix,
Please throw some inputs or links which can solve that "Rearrange in " O(M+N) time. Problem I see: when we identify the position for a[i+1][0], and we repace it with a[k][l], the a[k][l] which is now in a[i+1][0] must again be searched for its exact position example: -- current state 1 2 7 3 5 8 4 6 9 -- updating a[i+1][0] 1 2 3 7 5 8 4 6 9 -- assuming we try to fix the value in row first.. and then check column.. (and may be recursively) 1 2 3 5 7 8 -- now here there are two in consistancies (5,4 in col1, 7,6 in col2) 4 6 9 1 2 3 4 7 8 5 6 9 and 1 2 3 4 6 8 5 7 9 ====== or we doing this approach? and will this work? the choice that replaces 7 in this case is min of (5,4) 1 2 3 7 5 8 4 6 9 and.. recursively keep replacing the min (right, next-row_first-col) with the current, (this one is expected to take O(M+N-i-j) as u mentioned.) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/b8NPQMRwoD0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.