4,522 views

A two dimensional array $A[1..n][1..n]$ of integers is partially sorted if $\forall i, j\in [1..n-1], A[i][j] < A[i][j+1] \text{ and } A[i][j] < A[i+1][j]$

1. The smallest item in the array is at $A[i][j]$ where $i=\_\_$ and $j=\_\_$.

2. The smallest item is deleted. Complete the following $O(n)$ procedure to insert item $x$ (which is guaranteed to be smaller than any item in the last row or column) still 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



Clarify..
corrected..

https://gateoverflow.in/8148/gate2015-2_31

Young tableau

1. The smallest element is at index $1$,$1$.
2. So we have to give an array which is partially sorted. Definition of partially sorted is given in the question.
We will give the value of $x$ which is less than last row & column value.
At last, $1$,$1$ should be deleted & $x$ should be at its correct place.
  i=1;j=1; a[i][j]=x;
while ((x>a[i+1][j]) || (x>a[i][j+1]))
{
if((a[i+1][j] < x) && (a[i+1][j] <a[i][j+1]))
{
a[i][j]=a[i+1][j];
i=i+1;
}
else
{
a[i][j]=a[i][j+1];
j=j+1;
}
}
a[i][j]=x;


Enter the dimension of $n\times n$ array. Give the value of $n$
$3$
Enter the array elements in partially sorted order
$2$ $3$ $9$
$5$ $6$ $10$
$8$ $11$ $15$

Enter the value of $x$
$7$

The final output.
$3$   $6$   $9$
$5$   $7$   $10$
$8$   $11$ $15$

by

@eyeamgj Let's take a matrix of 4x4. Either you're gonna travel towards right or bottom if we're starting from the (1,1). So maximum path will be, if you traversed all the way to the bottom row i.e. (1,1) – (2,1) – (3,1) – (4,1) and then you traversed across all the way to the end element (4,4). At max this will take O(n+n). Therefore O(n)
OK THANK YOU GOT…...

@Ahwan Sir,

Amazing explanation !

(a). i=1 and j=1 (smallest item in the array)

(b).here in while loop (x>A[i+1][j] or x>A[i][j+1])

A[i][j]:=A[i+1][j]; i:=i+1;

else begin

A[i][j]:=A[i][j+1]; j=j+1;

end

A[i][j]:=x;

@Arjun sir, @Bikram sir the solution is wrong.
The question also seems little bit wrong.
I implemented it.
while (x>a[i+1][j] || x>a[i][j+1])
{
if(a[i+1][j] < a[i][j])
{
a[i][j]=a[i+1][j];
i=i+1;
}
else
{
a[i][j]=a[i][j+1];
j=j+1;
}
}

Output:

Enter the dimension of nxn array. Give the value of n
3
Enter the array elements in partially sorted order
2 3 9
5 6 10
8 11 15

Enter the value of x
7

The final output.
5   3   9
6   7   10
8   11   15

So 5 is at 1,1   3 should be at 1,1. It is not partially sorted.
after first iteration, j is not incremented. So,

7 3 9
5 6 10
8 11 15
becomes
5 3 9
5 6 10
8 11 15.

In next iteration, 5 should be replaced by 3 rt?
@Arjun sir,  j is not incremented but i is incremented.

The order in which it is modified...

Enter the array elements in partially sorted order
2 3 9
5 6 10
8 11 15

Enter the value of x
7

5   3   9
5   6   10
8   11   15

5   3   9
6   6   10
8   11   15

The final output.
5   3   9
6   7   10
8   11   15
yes, you are correct :)
Arjun Sir

For the first question, if input array A[4][4] is:

1 2 4 7

3 5 6 10

8 9 11 14

12 13 15 0

This array also obeys the basic condition A[i][j] <A[i+1][j] and A[i][j]<A[i][j+1] , for all i,j€[1,2,3]. But A[4][4] may contain the minimum value. So how we can confirm that A[1][1] will contain the minimum value.