Java find value in column wise sorted matrix

Question

I am currently in my first year of university and my teacher gave us an interesting problem

Given the 2 dimensional array m (the column length is equal to the row length for example 4x4, 3x3)

We know that if m goes through the function test it will return true

Now we need to write a function that based on that information will find the given value in m and return false or true if was found. In addition, the function must be with time complexity of O(n) or less when n is the length of row/column (For example if the matrix is 5x5 then n is 5). The function cannot use recursion

Here is function test:

public static boolean test(int [][] m)
{
 int n=m.length;
 for(int r=0; r<(n-1); r++)
      for (int c=0; c<n; c++)
           for (int i=0; i<n; i++)
                if(m[r][c] > m[r+1][i]) return false;
 return true;
}

Here is an example for a matrix that I came up with that returns true:

1, 3, 2, 5
10, 9, 7, 15
17, 25, 16, 20
50, 30, 28, 40

Here is a possible function signature:

public static boolean findValTest (int [][] m, int val)

Thanks for everyone who answers!

Answer 1

Update: Here's an O(nlogn) solution, we need further discussion to find a number in one column in O(1).

public static boolean findValTest(int[][] m, int val) {
    for (int c = 0; c < m.length; c++) {
        if (val < m[c][0] || val > m[c][m[c].length - 1]) continue;
        if (binarySearch(m, c, val)) return true;
    }
    return false;
}

private static boolean binarySearch(int[][] m, int col, int key) {
    int low = 0, high = m[col].length - 1;
    while (low <= high) {
        int mid = low + ((high - low) / 2);
        if (m[mid][col] < key) {
            low = mid + 1;
        } else if (m[mid][col] > key) {
            high = mid - 1;
        } else if (m[mid][col] == key) {
            return true;
        }
    }
    return false;
}

Answer 2

I have managed to figure it out. It is basically O(3n) but since 3 is constant it is O(n). Basically we use the first column to give us the index of two rows where the value might be in.

For example if we use the matrix we I gave as an example and the value is 16 we go like this: Is val between 1 and 10? No. Is val between 10 and 17? Yes Search second row and third row.

Here is the code(It is kinda long and ugly but hopefully you will understand it):

// We search in the first column between what two numbers the value is,
// Then we search for row of the first index, if not there we search the row of the other index
// Time Complexity: O(n). We go through the first column which is O(n) and then we go over 2 rows which is O(2n). Together its O(3n) but because 3 is constant the time is O(n)
public static boolean findValTest(int[][] m, int val) {
    int[] index = whichRows(m,val);
    
    if(index[0] == -1 && index[1] == -1) // Indicator that the number was found in the first column
        return true;
    if(index[1] == -1){
        // We search in only one row
        for(int i = 0; i < m.length - 1; i++){
            if(val == m[index[0]][i]) {
                return true;
            }
        }
    }
    else {
        // Search both given rows by index
        for(int i = 0; i < index.length; i++){
            for(int j = 0; j < m.length; j++) {
                if(val == m[index[i]][j])
                    return true;
            }
        }
    }
    
    return false;    
}

public static int[] whichRows(int[][] m, int val) {
    int[] index = {0,0}; int len = m.length;
    // -1 in the index indicates that only one row needs to be searched, or the first or the last
    if(m[len-1][0] < val) // Only the last row(Which contains the biggest numbers in the matrix) needs to be searched
    {
        index[0] = len-1; index[1] = -1;
    }
    else if(m[0][0] > val){ // Only the first row needs to be searched
        index[0] = 0; index[1] = -1;
    }
    else { // We search between 
        for(int i = 0; i < len - 1; i++){
            if(m[0][i] == val)
            {
                index[0] = -1; index[1] = -1;
                return index;
            }
            if(m[i][0] < val && val < m[i+1][0]){
                index[0] = i; index[1] = i +1;
                break;
            }
        }
    }
    return index;
}

Answer 3

just wanted to update you that your code doesn't work at certain times.

Wanted to give you a breakdown but unfortunately something came up and I will have to go for the next couple of days, so it is my hope that you fix whatever's plaguing your design. Try to test it with other numbers and see for yourself.

I tested it with the following matrix:

int[][] matrix = {
            {13, 2, 17, 29},
            {52, 54, 62, 73},
            {140, 120, 111, 100},
            {235, 245, 255, 265},
    };

and used 265 and 235 as inputs, to which the output was false.

Good luck :)