Check if value exists in two dimensional array with 1 loop (O(n))

Given a two dimensional array m:
When running the following method on m, the method returns true.

public static boolean what(int [][] m)
{
 int n=m.length;

 for(int x=0; x<n; x++)
 for (int y=0; y<(n-1); y++)
 if(m[x][y] > m[x][y+1]) return false;

 for(int x=0; x<n; x++)
 for (int y=0; y<(n-1); y++)
 if(m[y][x] > m[y+1][x]) return false;
 return true;
} 

I need to write a new method to check if val exists in array m in O(n) running time when n is the number of lines in array m.
The method will returnt true if the val exists in m, false if not.

public static boolean findValWhat (int [][] m, int val) 
{

}

I can do it easy with multiple loops but since I need to do it in one loop, I can’t figure out how it can be done.


Source: java

Leave a Reply