3
\$\begingroup\$

I had to write a code (as an exercise) that receives a 2D row wise and col wise sorted array and an element, and return true is the element exists in the array.

The first thing that came to mind when i heard "sorted" is binary search, but than i realized that the last element in each row isn't necessarily smaller than the first one in the next line.

So, i figured out that the best complexity will be O(n), and wrote the following code:

 public static boolean findN(int[][] a, int x) {
        if (a.length == 0 || a[0].length == 0 || x > a[a.length - 1][a[0].length - 1] || x < a[0][0]) {
            return false;
        }
        int LastRow = a.length - 1, Lastcol = a[0].length - 1, row = 0, col = 0;

        while (row <= LastRow) {
            if (a[row][col] == x) {
                return true;
            } else if (col < Lastcol) {
                col++;
            } else {
                col = 0;
                row++;
            }
        }
        return false;
    }

array example: 

arr = {{1,2,7,30},  
      {2,4,18,50},  
      {3,6,19,90},  
      {4,7,20,91}}
  • After realizing that the best complexity will be O(n), I googled this problem so I'm almost certain that I'm right (although some people are claiming that they can do it in O(log(n))), but am I really?
  • Any other thoughts and improvements are welcomed, thank you all in advance!
\$\endgroup\$
4
  • \$\begingroup\$ Find first row that has first element <= X. Find last row that has last element >= X. Execute binary search for rows in between. \$\endgroup\$ Commented Jan 3, 2020 at 15:46
  • \$\begingroup\$ Lat's take X=17. First row that has first element <=17: [0], last row that has last element >=17: [3]. If ill run binary search for all of this rows the complexity will be O(nlogn). \$\endgroup\$ Commented Jan 3, 2020 at 18:44
  • \$\begingroup\$ Your array example is misleading: The third column 7, 18, 16, 17 is not increasing. \$\endgroup\$ Commented Jan 3, 2020 at 20:09
  • \$\begingroup\$ Edited, same for 18 now. \$\endgroup\$ Commented Jan 3, 2020 at 20:32

1 Answer 1

Reset to default
4
\$\begingroup\$

Your function does a linear search over all elements of the nested array, until the given number is found, or all elements have been visited. The complexity is \$ O(mn) \$ for an \$ m \$-by-\$n \$ matrix. For a square \$ n \$-by-\$n \$ matrix that makes \$ O(n^2) \$, and not \$ O(n) \$ as you claimed.

This can be improved, but let's first do a

Review of your current implementation

The Java naming convention for variables is “lower camel case,” e.g. lastRow, lastCol instead of LastRow, LastCol.

The while-loop is a nested loop over all rows and columns in disguise, and can be more clearly written as nested for-loops:

int numRows = a.length;
int numCols = a[0].length;

for (int row = 0; row < numRows; row++) {
    for (int col = 0; col < numCols; col++) {
        if (a[row][col] == x) {
            return true;
        }
    }
}

This also restricts the scope of row and col to the minimum needed.

A better algorithm

Your implementation does not take advantage of the fact that the numbers are sorted in each row and in each column. A better algorithm is described in Search in a row wise and column wise sorted matrix on GeeksForGeeks:

  1. Start with top right element.
  2. Loop: compare this element e with x
    • if e = x, then return position of e, since we found x in the given matrix.
    • if e > x then move left to check elements smaller than e (if out of bound of matrix, then break and return false)
    • if e < x then move below to check elements greater than e (if out of bound of matrix, then break and return false)
  3. repeat until you find the element, or return false

I do not want to deprive you of the satisfaction of implementing it yourself. Just note that any element is now found after at most \$ m+n \$ steps, so the complexity is reduced from \$ O(mn) \$ to \$ O(m+n) \$ for an \$ m \$-by-\$n \$ matrix.

\$\endgroup\$
9
  • \$\begingroup\$ First of all, thank you for the naming convention correction, i totally missed it. But about the rest, I had do disagree: If ill change the loop the way you suggested, the complexity will be O(n^2) and I had to do it at the best complexity possible. For the geeksforgeeks algorithm - I wrote something similar before, and than i realized that >>the last element in each row isn't necessarily smaller than the first one in the next line. If you'll run this code, with my example array and 17 as element, you'll see this isn't working. \$\endgroup\$ Commented Jan 3, 2020 at 20:19
  • 1
    \$\begingroup\$ @RedYoel: It does not work for 17 because the third column in your example is not sorted in increasing order (as I remarked in a comment to your question). \$\endgroup\$ Commented Jan 3, 2020 at 20:20
  • 1
    \$\begingroup\$ @RedYoel: And there is no difference between your while-loop and the nested for-loops: Both iterate linearly over all array elements (until the number is found, or the end of the array reached). \$\endgroup\$ Commented Jan 3, 2020 at 20:22
  • \$\begingroup\$ Really sorry for the mistake, I didn't uploaded the question from my computer and it made a mess, corrected the example. I understand that there is no difference between my while and the nested for loops, but mine goes for O(n), and the nested for loops goes for O(n^2) so it's better to do it on my way, no? \$\endgroup\$ Commented Jan 3, 2020 at 20:30
  • 1
    \$\begingroup\$ @RedYoel: If n denotes the dimension (i.e. the row/column count) then your while loop is O(n^2) as well. \$\endgroup\$ Commented Jan 3, 2020 at 20:33

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.