Saturday, August 27, 2011

Find a element in an 2D array

Given a 2D array of size NxN, whose rows and columns are sorted individually in ascending order from the top left corner.
Now given a number X you need to find the position of the number in the array.

Now lets say the element X(INT_MAX) in the array signifies the empty space in the array and lies always at the bottom right. How would insert an element by replacing this space in such a place so that the property of the array is maintained. (The only operation allowed is to swap two adjacent elements which share an edge.)

Similarly how would you delete an element from the array and replace it with the X