A two-dimensional array A[1..n][1..n] of pairwise distinct integers, where n ≥…

PYQ GATE 1996Modified — slightly modified from the official paper; see the solution

A two-dimensional array A[1..n][1..n] of pairwise distinct integers, where n ≥ 2, is partially sorted if every row and every column is strictly increasing:

A[i][j] < A[i][j+1] for 1 ≤ i ≤ n, 1 ≤ j < n;
A[i][j] < A[i+1][j] for 1 ≤ i < n, 1 ≤ j ≤ n.

Fill in the blanks:

(a) The smallest item in the array is at A[i][j], where i = ____ and j = ____.

(b) The smallest item is deleted. Complete the following O(n) procedure to insert item x, which is distinct from every remaining item and smaller than every item in the last row or column, while keeping A partially sorted.

procedure insert(x: integer);
var i, j: integer;
begin
    i := 1; j := 1; A[i][j] := x;
    while (x > ____ or x > ____) do
        if A[i+1][j] < A[i][j] ____ then begin
            A[i][j] := A[i+1][j]; i := i+1;
        end
        else begin
            ____
        end;
    A[i][j] := ____;
end;

Attempted by 2 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…