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\$
  • \$\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\$ – TorbenPutkonen Jan 3 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\$ – RedYoel Jan 3 at 18:44
  • \$\begingroup\$ Your array example is misleading: The third column 7, 18, 16, 17 is not increasing. \$\endgroup\$ – Martin R Jan 3 at 20:09
  • \$\begingroup\$ Edited, same for 18 now. \$\endgroup\$ – RedYoel Jan 3 at 20:32
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.

|improve this answer|||||
\$\endgroup\$
  • \$\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\$ – RedYoel Jan 3 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\$ – Martin R Jan 3 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\$ – Martin R Jan 3 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\$ – RedYoel Jan 3 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\$ – Martin R Jan 3 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.