1

I recently sat in an interview and I was asked this question:

Given a 2d array of integers, where:

  • Every row is sorted from left to right.

  • Every column is sorted from top to bottom.

What is the best algorithm for finding the position of an element x?

I was happy, as I had done this before, and this was my answer:

Start at the top right position.

If e at that position is greater than x,then definitely, all elements of that column are greater than x and we move one column back.

If e at that position is less than x, then definitely all the elements behind e are less than x and all elements after e are greater than x and so we move one row down,

If e==x, we stop or we keep doing this,until we hit the left boundary or the bottom boundary and if we hit a boundary before we find e==x,then the 2d array does not contain that element.

Clearly, the time complexity of this method is O(n) for nXn matrix, but the interviewer insisted on a logrithmic approach, and I was unable to reach anywhere near O(log n).

My question is, can it be done in O(log n)?

Bor
  • 775
  • 3
  • 19
  • 44
Sumeet
  • 8,086
  • 3
  • 25
  • 45
  • 1
    I think someone answered this already in this thread: http://stackoverflow.com/questions/2457792/given-a-2d-array-sorted-in-increasing-order-from-left-to-right-and-top-to-bottom – DaniG2k Aug 26 '15 at 13:29

1 Answers1

2

Yes it can be done, you just need to do a binary search. 

public int searchMatrix(ArrayList<ArrayList<Integer>> A, int B) {
    int row, col;
    int m, n;
    if (A == null)
        return 0;
    m = A.size();
    if (m == 0)
        return 0;
    n = A.get(0).size();
    row = 0;
    col = n - 1;
    while (checkBound(row, col, m, n)) {
        if (B == A.get(row).get(col))
            return 1;
        int num = A.get(row).get(col);

        if (B < num)
            col--;
        else if (B > num)
            row++;
    }
    return 0;
}

public boolean checkBound(int row, int col, int m, int n) {
    return (row >= 0 && row < m && col >= 0 && col < n);

}

Michael Lasso
  • 50
  • 5