- Algorithms Question Assumptions Integers In Each Row Are Sorted In Ascending From Left To Right Integers In Each Colu 1 (22.32 KiB) Viewed 42 times
Integers in each row are sorted in ascending from left toright.
Integers in each column are sorted in ascending from top tobottom.
Special Assumptions:
The matrix may have missing elements. If that is the case: thecell value will be replaced with a special value called INF. Thinkof INF as a value that is bigger than any number (similar toinfinity in mathematics).
If a row contains this INF value, it will be the last value onthe row.
If a column contains this INF value, it will be the last valueon the column.
Example: if our matrix contains one INF value (and the rest arenumbers), the INF value will be located at the bottom row of therightmost column.
If our matrix has NO numbers, all cells will have INF values
Question:
Create an efficient algorithm in pseudocode called minVal(B, n)where B is a non-empty n x n matrix, which returns the smallestelement of B (element located in row 1, column 1) having theassumptions of the matrix as described. Since we are removing anumber from the matrix, after the algorithm runs, the matrix willcontain one more INF value. The algorithm must be in-place thusadditional matrix can be used. (n is the number of rows)
Hint: Think BuildMaxHeap and recursionFAQ:There can be duplicate values in the matrix, they can be added tothe matrix too.
There can be multiple valid cells for a number.
147 11 15 5 8 12 19 6 9 16 22 2 3 10 13 14 17 14 17 24 18 21 23 26 30