4,518 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

nice explanation @Ahwan

Superb 🙌

@Ahwan

@Ahwan I ran this code on the following input

1 2 3 4

2 3 4 5

3 4 5 6

4 5 6 7

This DD array is partially sorted according to the definition given in the problem.

I tried to insert x=3 , which is lesser than items in the last row and column . I ran the code on this input and got the following output.

2 3 3 4

2 3 4 5

3 4 5 6

4 5 6 7

but this is not partially sorted , can you help me here?

@prashant jha 1

If you are saying that $\begin{bmatrix} 2& 3& 3& 4\\ 2& 3& 4& 5\\ 3& 4& 5& 6\\ 4& 5& 6& 7\end{bmatrix}$ is not partially sorted because A[i][j] is not strictly less than A[i+1][j] and A[i][j+1] $\forall$i,j.

Then I think we can't have a partially sorted order for this array. The smallest element is '2' and it must be placed in A, and we still have one more occurrence of '2' which has to be in A or A. But placing '2' in A or A makes the array not in partially sorted order.

PS: I think they have assumed array of distinct elements.

can any one explian why the time complexity is O(n)?
@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,  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 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 may contain the minimum value. So how we can confirm that A will contain the minimum value.