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


  1. What about a log(n) * log(n) solution? First using binary search look for the row containing our element; once we have the row, use again binary search to spot our number.


  2. Hello Sir,
    We can just start from the element arr[0][n].Because this is the only place where we have a choice to move on the array downwards and upwards depending in the comparison of the given number and the numbers at the left and just below the current position.
    When we get the required number we stop.
    Please give ur opinion on the approach.

  3. @landimatte ... how will you search for the row in log(n). Suppose the array is

    1 2 3 4
    2 5 8 9
    3 7 10 11
    6 9 12 23

    Now if the number to found is 8 .. what will be your approach ?

  4. @vivek .. yeah nice ... it can be improved a bit further from the O(n+n) complexity ... perhaps landimatte will explain his elegant approach ....

  5. Nevermind; misunderstood the problem and given also a wrong complexity answer!!!!
    However, what is the supposed solution complexity?

  6. Let's try again: what about using binary search on each step of the algorithm presented by Vivek?

    Start from the top left element: if its value is greater than our target, then do binary search on the row, in order to find the closest element to the target; otherwise, if the current element was smaller than the target, do binary search on the column, in order to find the closest element to the target.
    Repeat until desired element is found.

    What do you think about that?

  7. @landimatte ... yeah i would say the average case would definitely improve but the worst case still remains to be O(n).
    The best solution is lg(n)*lg(n)


  8. Do a binary search on the diagonal of the matrix.
    If we find the number then that is the answer.
    If we don't find the number then we know the number lies between two numbers having indexes (i,i) and (i+1,i+1).
    We can ignore the matrix (0, 0) to (i, i) as all the numbers will be less than the number we need.
    We can ignore the matrix (i+1, i+1) to (n-1,n-1) as all the numbers will be more than the number we need.
    We are now remaining with matrices (0, i+1) to (i, n-1) and (i+1, 0) to (n-1, i) which we have to search recursively in a similar fashion.

  9. The worst case complexity of my solution is n*log(n), where n is number of rows/columns.

  10. Sorry the worst case complexity of my solution is O(n)
    First diagonal we are scanning log(n) times.
    Next we get two half matrices which we scan for log(n/2) times.
    So the series will be log(n)+2*log(n/2)+4*log(n/4)+...+2^(log(n)-1)
    Solving this we get n-(log(n)+1)/2
    So the worst case complexity is O(n)

  11. Vivek's algo doesn't work.
    1 5 6 7
    2 3 4 8
    9 10 11 12
    13 14 15 16
    Would it have really found 4 in this matrix?