we have a mn Matrix each element contains an integer or infi

we have a m*n Matrix. each element contains an integer or (infinity sign) . value of each row(form left to right) and each colun(from up to down) is not-decreasable.
find an algorithm from Order O(m+n) which finds the biggest integer.

Solution

Given an m* n Matriix, and each row are arranged by the elements in non-decreasing order, and also each columns are arranged with the elements in non-decreasing order. Also as stated, an element may be an infinite.

To find the biggest element in the array in O(m+n) times, We have to scan entire array in two phase.

In phase-1, scan each elements in the 1^st column to find the biggest element present in 1^st column only. and also find the index of the row where biggest element is present

In phase-2 scan each elements in the row computed in phase-2, to find the biggest element in that row only.

As the biggest element in the row is also the biggest in its column ,so this biggest element is the biggest in the entire array.

BiggestElement(A,m,n)

//This algorithm takes matrix A with size mXn as input. Computes the biggest element in O(m+n) times.It assumes the index of first element is [1,1]

1. Max=A[1,1]

//Phase -1

2. FOR i=2 to m

3. IF A[i ,1] ! =INFINITY and max<=A[i,1]

4. Max=A[i,1]

5. Row=i

6. ENDIF

7. ENDFOR

// Phase-2

8. FOR j=2 to n

9. IF A[row,j] ! =INFINITY and max<=A[row,j]

10 Max=A[row,j]

11 ENDIF

12. ENDFOR

13. RETURN Max

As in above procedure, We scanned each element in the matrix in one column and then scan each element only in the row where we find biggest element.

As there are m rows, (in phase-1) scanning each element in one column O(m)

As there are n columns ,(in phase-2) scanning each element in a row takes O(n) times.

So total time= O(m+n)