CareerCup

Got some idea,
1. for-loop every row, find the maximum value of the row, and save its index into an array, e.g: row[i] = index of maximum
2. for-loop every column, find the minimum value of the column, and save its index into another array. e.g: col[j] = index of minimum.

3. Check row[i], col[j], i,j, if we can find a pair, row[i]=j, and col[j]=i, then the m[j][i] is the result.

for example: matrix m[4][4] as following
3, 5, 9, 4
1, 10,11,6
8, 7, 14,13
12,2,16,15

row[0]=2, col[0]=1,
row[1]=2, col[1]=3,
row[2]=2, col[2]=0,
row[3]=2, col[3]=0,

row[0]=2 and col[2]=0, so the result is m[0][2] is the result.

for example2: change the m[0][2] from 9 to 19, the col[2] = 1.
so, this time the answer is row[1]=2 and col[2]=1, m[1][2]

Time is O(n^2), Space is O(c)

Let 'm' be the number of rows and 'n' be the number of columns.
Let row_max[m] and col_min[n] be two separate arrays such that row_max[i] contains the the maximum element of ith row and col_min[j] contains the minimum element of the jth column.

for every value in row_max
{
if the same value is found in col_min then
the element is the minimum in column and maximum in row
}
Time Complexity: O(m*n)
Space Complexity: O(m+n)

I am not sure if the above solution is correct. If something is wrong please point it out.

calculate the maximum in a row, in the loop and save its indexes(imax,jmax).
now, find in column jmax lowest element by iterating over i. only one element is required so no extra space required.

min = INT_MAX;max = INT_MIN; imax = jmax = -1;
for(i=0;i<row;i++)
{
  for(j=0;j<col;j++)
  {
   if(a[i][j]>max) {imax = i; jmax = j; max = a[i][j];}
  }
  

  for(j=0;j<row;j++)
  {
   if(a[j][jmax]<min) { imin = j; min = a[j][jmax];}
  }
  
  if(imin == imax){printf("found at  %d %d",imax,jmax)return;}
  //reinitialise max and min

}

they asked to optimize this to constant amount of time

Is there anyway which can find the target value without traversing the whole 2D array?

No....

int main()
{
    int a[10][10];
    int i,j;
    int m,n;
    int max;
    int val;
    printf("Enter the No. of rows && cols :");
    scanf("%d\t%d",&m,&n);
    printf("Enter the Elememts :\n");
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            scanf("%2d",&a[i][j]);
        }
        printf("\n");
    }
    for(i=0;i<m;i++)
    {
        max=a[i][0];
        for(j=0;j<n;j++)
        {
           if(a[i][j]>max) {
               max=a[i][j];
               val=j;
               }
        }
        if(isMinColumn(a,val,m,max))
         {
           printf("Element found :%d",max);
           printf("\n");
             break;
         }
    }
    getchar();
    return 0;
}
int isMinColumn (int a[][10],int col,int n,int value)
{
  int min=a[0][col];
  int i;
  for(i=0;i<n;i++)
  {
   if(a[i][col]<value)

{
      return 0;
    }
  }
  return 1;
}

I think this will work in constant time

Find maxelement in 1st row ...check if thats the minimum value in its column
Move to next row and repeat the same

int FindElement(int a[4][5],int m,int n){
if(m==0 && n==0) return -1;
int i=0,j=0;
int index=0;
int maxElement,maxIndex,flag;
while(index<m){
flag=0;
maxElement=a[index][0];
maxIndex=0;
for(i=0;i<n;i++){
if(a[index][i]>maxElement){
maxElement=a[index][i];
maxIndex=i;
}
}
j=maxIndex;
for(i=0;i<m;i++){
if(a[i][j]<maxElement){
flag=1;
continue;
}
}
if(flag==0)
return maxElement;
index++;
}
return -1;
}

thats not constant time...

MME()			
	for each i from 0 to n-1
		for each j from 0 to m-1
			if(a[i][j] > max)
				maxj =j
		for each i from 0 to n-1
			if(a[i][maxj] < min)
				mini = i
		if(i == mini)
			print a[i][maxj]

first sort the Matrix.So First row last column will be Maximum of row and minimum of column.

Find the sums for all the columns and the rows. The intersection element of the column that has the max sum and the row that has the max sum is the needed element.

Steps:
1. Take two auxiliary arrays r[] & c[].
r[i] would be containing the column number of the largest number in the row i.
c[i] would be containing the row number of the smallest number in the column i.

Now find a i such that arr[i][r[i]] is equal to arr[col[j]][j].
This would give the intersection of the row having largest number with column having minimum number.

Here is the sample code:

void foo(int (*arr)[COL])
{
        int r[ROW],c[COL],i,j,max;
        for(i=0;i<ROW;i++)
        {
                max=0;
                for(j=0;j<COL;j++)
                        if(arr[i][j]>arr[i][max])
                                max=j;
                r[i]=max;
        }
 
        for(i=0;i<COL;++i)
        {
                max=0;
                for(j=0;j<ROW;++j)
                        if(arr[j][i]<arr[max][i])
                                max=j;
                c[i]=max;
        }
 
        for(i=0;i<ROW;++i)
                for(j=0;j<COL;++j)
                        if(arr[i][r[i]]==arr[c[j]][j])
                                printf("%d ",arr[i][r[i]]);
}

Complete code here: ideone.com/1OYSZ

This can be done in O(1) space.
Time complexity: O(MxN)

Find the max item in the row. Check whether it is the smallest in the column.

void foo(int (*arr)[COL])
{
        int i,j,max, min;
        for( i = 0; i < ROW; i++ )
        {
                max=0;
                for( j = 1; j < COL; j++ ) // find max in the row
                        if(arr[i][j] > arr[i][max])
                                max=j;
 
                min = 0;
                for( j = 1; j < ROW; ++j ) // find min in the column
                        if(arr[j][max] < arr[min][max])
                                min=j;
 
                if( min == i ) // if both items are same
                        printf("%d", arr[i][max]);
        }
}

Here is the working code: ideone.com/XfGJV

here you can find a good answer
javaques.com/how-to-find-minimum-and-maximum-value-stored-in-a-2d-array/