Posted on by Kalkicode
Code Matrix

# Print K’th element in spiral form of matrix

The code provided focuses on the problem of finding the K'th element in the spiral traversal of a given matrix. This problem involves traversing the matrix in a spiral manner, extracting elements in a specific order, and identifying the K'th element based on this traversal.

## Problem Statement

Given a matrix and a positive integer K, the goal is to determine the K'th element when the matrix is traversed in a spiral manner, starting from the top-left corner and moving towards the center.

## Example

Consider the following matrix:

`````` 1   2   3   4   5   6
7   8   9  10  11  12
13  14  15  16  17  18
19  20  21  22  23  24
25  26  27  28  29  30
31  32  33  34  35  36
37  38  39  40  41  42``````

For K = 9, the 9'th element in the spiral traversal is 24.

For K = 21, the 21'st element is 13.

For K = 42, the 42'nd element is 21.

## Solution Idea

To solve this problem, the matrix is traversed in a spiral order by moving in four directions: left to right, top to bottom, right to left, and bottom to top. The K'th element is identified during this traversal.

## Pseudocode

``````spiral(data, s_row, s_col, e_row, e_col, k):
result = 0
# Traverse left to right
for i from s_col to e_col and k > 0:
if k == 1:
result = data[s_row][i]
k--
# Traverse top to bottom
for i from s_row + 1 to e_row and k > 0:
if k == 1:
result = data[i][e_col]
k--
# Traverse bottom right to bottom left
for i from e_col - 1 down to s_col and k > 0:
if k == 1:
result = data[e_row][i]
k--
# Traverse bottom left to top
for i from e_row - 1 down to s_row + 1 and k > 0:
if k == 1:
result = data[i][s_col]
k--
if k == 0:
print result
if s_row + 1 <= e_row - 1 and k > 0:
spiral(data, s_row + 1, s_col + 1, e_row - 1, e_col - 1, k)

kth_element(arr, k):
if k < 0 or k > COL * ROW:
print "Element does not exist"
else:
print "Spiral", k, "'th Element : "
spiral(arr, 0, 0, ROW - 1, COL - 1, k)``````

## Algorithm Explanation

1. The `spiral` function performs the spiral traversal within the given bounds and identifies the K'th element. It starts by traversing left to right, then top to bottom, right to left, and finally bottom to top.
2. The `kth_element` function takes the matrix and K as input. It first checks if K is within the valid range. If it is, it initiates the spiral traversal to identify the K'th element.

## Code Solution

``````/*
C Program
+ Print K’th element in spiral form of matrix
*/
#include<stdio.h>
#define ROW 7
#define COL 6

void spiral(int data[ROW][COL],
int s_row,
int s_col,
int e_row,
int e_col,
int k)
{
int result=0;
//Left to right
for (int i = s_col; i <=e_col && k > 0 ; ++i,k--)
{
if(k==1)
{
result=data[s_row][i];

}
}
//Top to down
for (int i = s_row+1; i <=e_row && k > 0  ; ++i,k--)
{
if(k==1)
{
result=data[i][e_col];
}

}
//Bottom right to bottom-left
for (int i = e_col-1; i >=s_col && k > 0 ; --i,k--)
{
if(k==1)
{
result=data[e_row][i];
}

}

//Bottom left to top
for (int i =e_row-1 ; i > s_row && k > 0 ; --i,k--)
{
if(k==1)
{
result=data[i][s_row];
}

}
if(k==0)
{
printf("%d\n",result );
}

if(s_row+1 <= e_row-1 && k > 0)
{
//Recursive call
spiral(data,s_row+1,s_col+1,e_row-1,e_col-1,k);
}

}
void kth_element(int arr[ROW][COL],int k)
{

if(k < 0 || k > COL*(ROW))
{
//invalid input
printf("Element not exist %d\n",k);
}
else
{
printf("Spiral %d'th Element : ", k);
spiral(arr,0,0,ROW-1,COL-1,k);
}
}
int main(){

int arr[ROW][COL]={
{1,  2,  3,   4,  5, 6},
{7,  8,  9,   10, 11, 12},
{13, 14, 15,  16, 17, 18},
{19, 20, 21,  22, 23, 24},
{25, 26, 27,  28, 29, 30},
{31, 32, 33,  34, 35, 36},
{37, 38, 39,  40, 41, 42},
};

kth_element(arr,9);
kth_element(arr,21);
kth_element(arr,42);
return 0;
}```
```

#### Output

``````Spiral 9'th Element : 24
Spiral 21'th Element : 13
Spiral 42'th Element : 21``````
``````/*
C++ Program
Print K’th element in spiral form of matrix
*/
#include<iostream>
#define ROW 7
#define COL 6
using namespace std;

class MyMatrix {
public:

void spiral(int matrix[ROW][COL],
int s_row,
int s_col,
int e_row,
int e_col,
int k)
{
int result=0;
//Left to right
for (int i = s_col; i <=e_col && k > 0 ; ++i,k--)
{
if(k==1)
{
result=matrix[s_row][i];

}
}
//Top to down
for (int i = s_row+1; i <=e_row && k > 0  ; ++i,k--)
{
if(k==1)
{
result=matrix[i][e_col];
}

}
//Bottom right to bottom-left
for (int i = e_col-1; i >=s_col && k > 0 ; --i,k--)
{
if(k==1)
{
result=matrix[e_row][i];
}

}

//Bottom left to top
for (int i =e_row-1 ; i > s_row && k > 0 ; --i,k--)
{
if(k==1)
{
result=matrix[i][s_row];
}
}
if(k==0)
{
cout<<"  "<<result <<endl;
}
if(s_row+1 <= e_row-1 && k > 0)
{
//Recursive call
spiral(matrix,s_row+1,s_col+1,e_row-1,e_col-1,k);
}

}
void kth_element(int matrix[ROW][COL],int k)
{

if(k < 0 || k > COL*(ROW))
{
//invalid input
cout<<" Element "<<k<<" not exist \n";
}
else
{
cout<<" Spiral "<<k<<"'th Element : ";
spiral(matrix,0,0,ROW-1,COL-1,k);
}
}
};
int main() {
MyMatrix obj;
int matrix[][COL] ={
{1,  2,  3,   4,  5, 6},
{7,  8,  9,   10, 11, 12},
{13, 14, 15,  16, 17, 18},
{19, 20, 21,  22, 23, 24},
{25, 26, 27,  28, 29, 30},
{31, 32, 33,  34, 35, 36},
{37, 38, 39,  40, 41, 42},
};

obj.kth_element(matrix,9);
obj.kth_element(matrix,21);
obj.kth_element(matrix,42);

return 0;
}```
```

#### Output

`````` Spiral 9'th Element :   24
Spiral 21'th Element :   13
Spiral 42'th Element :   21``````
``````/*
Java Program
Print K’th element in spiral form of matrix
*/
public class MyMatrix {

public void spiral(int [][]matrix,
int s_row,
int s_col,
int e_row,
int e_col,
int k)
{

int result=0;
//Left to right
for (int i = s_col; i <=e_col && k > 0 ; ++i,k--)
{
if(k==1)
{
result=matrix[s_row][i];

}
}
//Top to down
for (int i = s_row+1; i <=e_row && k > 0  ; ++i,k--)
{
if(k==1)
{
result=matrix[i][e_col];
}

}
//Bottom right to bottom-left
for (int i = e_col-1; i >=s_col && k > 0 ; --i,k--)
{
if(k==1)
{
result=matrix[e_row][i];
}

}

//Bottom left to top
for (int i =e_row-1 ; i > s_row && k > 0 ; --i,k--)
{
if(k==1)
{
result=matrix[i][s_row];
}
}
if(k==0)
{
System.out.print("  "+result );
}

if(s_row+1 <= e_row-1 && k > 0)
{
//Recursive call
spiral(matrix,s_row+1,s_col+1,e_row-1,e_col-1,k);
}

}
public void kth_element(int [][]matrix,int k)
{
//Find the array size
int row =matrix.length;
int col =matrix[0].length;

if(k < 0 || k > col*row)
{
//invalid input
System.out.print("\n Element "+k+" not exist ");
}
else
{
System.out.print("\n Spiral "+k+"'th Element : ");
spiral(matrix,0,0,row-1,col-1,k);
}
}
public static void main(String[] args) {
MyMatrix obj = new MyMatrix();
//Define matrix
int [][]matrix ={
{1,  2,  3,   4,  5, 6},
{7,  8,  9,   10, 11, 12},
{13, 14, 15,  16, 17, 18},
{19, 20, 21,  22, 23, 24},
{25, 26, 27,  28, 29, 30},
{31, 32, 33,  34, 35, 36},
{37, 38, 39,  40, 41, 42},
};
obj.kth_element(matrix,9);
obj.kth_element(matrix,21);
obj.kth_element(matrix,42);
}
}```
```

#### Output

`````` Spiral 9'th Element :   24
Spiral 21'th Element :   13
Spiral 42'th Element :   21``````
``````/*
C# Program
Print K’th element in spiral form of matrix
*/
using System;
public class MyMatrix {
public void spiral(int[,] matrix, int s_row, int s_col, int e_row, int e_col, int k) {
int result = 0;
//Left to right

for (int i = s_col; i <= e_col && k > 0; ++i, k--) {
if (k == 1) {
result = matrix[s_row,i];
}
}
//Top to down

for (int i = s_row + 1; i <= e_row && k > 0; ++i, k--) {
if (k == 1) {
result = matrix[i,e_col];
}
}
//Bottom right to bottom-left

for (int i = e_col - 1; i >= s_col && k > 0; --i, k--) {
if (k == 1) {
result = matrix[e_row,i];
}
}
//Bottom left to top

for (int i = e_row - 1; i > s_row && k > 0; --i, k--) {
if (k == 1) {
result = matrix[i,s_row];
}
}
if (k == 0) {
Console.Write(" " + result);
}
if (s_row + 1 <= e_row - 1 && k > 0) {
spiral(matrix, s_row + 1, s_col + 1, e_row - 1, e_col - 1, k);
}
}
public void kth_element(int[,] matrix, int k) {
//Find the array size
int row = matrix.GetLength(0);
int col = matrix.GetLength(1);
if (k < 0 || k > col * row) {
Console.Write("\n Element " + k + " not exist ");
} else {
Console.Write("\n Spiral " + k + "'th Element : ");
spiral(matrix, 0, 0, row - 1, col - 1, k);
}
}
public static void Main(String[] args) {
MyMatrix obj = new MyMatrix();
int[,]
//Define matrix
matrix = {
{
1,
2,
3,
4,
5,
6
},
{
7,
8,
9,
10,
11,
12
},
{
13,
14,
15,
16,
17,
18
},
{
19,
20,
21,
22,
23,
24
},
{
25,
26,
27,
28,
29,
30
},
{
31,
32,
33,
34,
35,
36
},
{
37,
38,
39,
40,
41,
42
}

};
obj.kth_element(matrix, 9);
obj.kth_element(matrix, 21);
obj.kth_element(matrix, 42);
}
}```
```

#### Output

`````` Spiral 9'th Element :  24
Spiral 21'th Element :  13
Spiral 42'th Element :  21``````
``````<?php
/*
Php Program
Print K’th element in spiral form of matrix
*/
class MyMatrix {
public 	function spiral(\$matrix, \$s_row, \$s_col, \$e_row, \$e_col, \$k) {
\$result = 0;
//Left to right

for (\$i = \$s_col; \$i <= \$e_col && \$k > 0; ++\$i, \$k--) {
if (\$k == 1) {
\$result = \$matrix[\$s_row][\$i];
}
}
//Top to down

for (\$i = \$s_row + 1; \$i <= \$e_row && \$k > 0; ++\$i, \$k--) {
if (\$k == 1) {
\$result = \$matrix[\$i][\$e_col];
}
}
//Bottom right to bottom-left

for (\$i = \$e_col - 1; \$i >= \$s_col && \$k > 0; --\$i, \$k--) {
if (\$k == 1) {
\$result = \$matrix[\$e_row][\$i];
}
}
//Bottom left to top

for (\$i = \$e_row - 1; \$i > \$s_row && \$k > 0; --\$i, \$k--) {
if (\$k == 1) {
\$result = \$matrix[\$i][\$s_row];
}
}
if (\$k == 0) {
echo(" ". \$result);
}
if (\$s_row + 1 <= \$e_row - 1 && \$k > 0) {
//Recursive call
\$this->spiral(\$matrix, \$s_row + 1, \$s_col + 1, \$e_row - 1, \$e_col - 1, \$k);
}
}
public 	function kth_element(\$matrix, \$k) {
//Find the array size
\$row = count(\$matrix);
\$col = count(\$matrix[0]);
if (\$k < 0 || \$k > \$col *\$row) {
//invalid input

echo("\n Element ". \$k ." not exist ");
} else {
echo("\n Spiral ". \$k ."'th Element : ");
\$this->spiral(\$matrix, 0, 0, \$row - 1, \$col - 1, \$k);
}
}
};

function main() {
\$obj = new MyMatrix();
//Define matrix
\$matrix = array(
array(1, 2, 3, 4, 5, 6),
array(7, 8, 9, 10, 11, 12),
array(13, 14, 15, 16, 17, 18),
array(19, 20, 21, 22, 23, 24),
array(25, 26, 27, 28, 29, 30),
array(31, 32, 33, 34, 35, 36),
array(37, 38, 39, 40, 41, 42)
);
\$obj->kth_element(\$matrix, 9);
\$obj->kth_element(\$matrix, 21);
\$obj->kth_element(\$matrix, 42);

}
main();```
```

#### Output

`````` Spiral 9'th Element :  24
Spiral 21'th Element :  13
Spiral 42'th Element :  21``````
``````/*
Node Js Program
Print K’th element in spiral form of matrix
*/
class MyMatrix {
spiral(matrix, s_row, s_col, e_row, e_col, k) {
var result = 0;
//Left to right

for (var i = s_col; i <= e_col && k > 0; ++i, k--) {
if (k == 1) {
result = matrix[s_row][i];
}
}

//Top to down

for (var i = s_row + 1; i <= e_row && k > 0; ++i, k--) {
if (k == 1) {
result = matrix[i][e_col];
}
}

//Bottom right to bottom-left

for (var i = e_col - 1; i >= s_col && k > 0; --i, k--) {
if (k == 1) {
result = matrix[e_row][i];
}
}

//Bottom left to top

for (var i = e_row - 1; i > s_row && k > 0; --i, k--) {
if (k == 1) {
result = matrix[i][s_row];
}
}

if (k == 0) {
process.stdout.write(" " + result);
}

if (s_row + 1 <= e_row - 1 && k > 0) {
//Recursive call
this.spiral(matrix, s_row + 1, s_col + 1, e_row - 1, e_col - 1, k);
}
}
kth_element(matrix, k) {
//Find the array size
var row = matrix.length;
var col = matrix[0].length;
if (k < 0 || k > col *row) {
//invalid input

process.stdout.write("\n Element " + k + " not exist ");
} else {
process.stdout.write("\n Spiral " + k + "'th Element : ");
this.spiral(matrix, 0, 0, row - 1, col - 1, k);
}
}
}

function main(args) {
var obj = new MyMatrix();
//Define matrix
var matrix = [
[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24],
[25, 26, 27, 28, 29, 30],
[31, 32, 33, 34, 35, 36],
[37, 38, 39, 40, 41, 42]
];
obj.kth_element(matrix, 9);
obj.kth_element(matrix, 21);
obj.kth_element(matrix, 42);
}
main();```
```

#### Output

`````` Spiral 9'th Element :  24
Spiral 21'th Element :  13
Spiral 42'th Element :  21``````
``````# Python 3 Program
#   Print K’th element in spiral form of matrix
class MyMatrix :
def spiral(self, matrix, s_row, s_col, e_row, e_col, k) :
result = 0
# Left to right
i = s_col
while (i <= e_col and k > 0) :
if (k == 1) :
result = matrix[s_row][i]

i += 1
k -= 1

# Top to down
i = s_row + 1
while (i <= e_row and k > 0) :
if (k == 1) :
result = matrix[i][e_col]

i += 1
k -= 1

# Bottom right to bottom-left
i = e_col - 1
while (i >= s_col and k > 0) :
if (k == 1) :
result = matrix[e_row][i]

i -= 1
k -= 1

# Bottom left to top
i = e_row - 1
while (i > s_row and k > 0) :
if (k == 1) :
result = matrix[i][s_row]

i -= 1
k -= 1

if (k == 0) :
print(" ", result, end = "")

if (s_row + 1 <= e_row - 1 and k > 0) :
self.spiral(matrix, s_row + 1, s_col + 1, e_row - 1, e_col - 1, k)

def kth_element(self, matrix, k) :
row = len(matrix)
col = len(matrix[0])
if (k < 0 or k > col * row) :
print("\n Element ", k ," not exist ", end = "")
else :
print("\n Spiral ", k ,"'th Element : ", end = "")
self.spiral(matrix, 0, 0, row - 1, col - 1, k)

def main() :
obj = MyMatrix()
matrix = [
[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24],
[25, 26, 27, 28, 29, 30],
[31, 32, 33, 34, 35, 36],
[37, 38, 39, 40, 41, 42]
]
obj.kth_element(matrix, 9)
obj.kth_element(matrix, 21)
obj.kth_element(matrix, 42)

if __name__ == "__main__":
main()```
```

#### Output

`````` Spiral  9 'th Element :   24
Spiral  21 'th Element :   13
Spiral  42 'th Element :   21``````
``````# Ruby Program
# Print K’th element in spiral form of matrix
class MyMatrix
def spiral(matrix, s_row, s_col, e_row, e_col, k)
result = 0
# Left to right
i = s_col
while (i <= e_col and k > 0)
if (k == 1)
result = matrix[s_row][i]
end
i += 1
k -= 1
end
# Top to down
i = s_row + 1
while (i <= e_row and k > 0)
if (k == 1)
result = matrix[i][e_col]
end
i += 1
k -= 1
end
# Bottom right to bottom-left
i = e_col - 1
while (i >= s_col and k > 0)
if (k == 1)
result = matrix[e_row][i]
end
i -= 1
k -= 1
end
# Bottom left to top
i = e_row - 1
while (i > s_row and k > 0)
if (k == 1)
result = matrix[i][s_row]
end
i -= 1
k -= 1
end
if (k == 0)
print(" ", result)
end
if (s_row + 1 <= e_row - 1 and k > 0)
self.spiral(matrix, s_row + 1, s_col + 1, e_row - 1, e_col - 1, k)
end
end
def kth_element(matrix, k)
row = matrix.length
col = matrix[0].length
if (k < 0 or k > col * row)
print("\n Element ", k ," not exist ")
else
print("\n Spiral ", k ,"'th Element  :")
self.spiral(matrix, 0, 0, row - 1, col - 1, k)
end
end
end
def main()
obj = MyMatrix.new()
matrix = [
[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24],
[25, 26, 27, 28, 29, 30],
[31, 32, 33, 34, 35, 36],
[37, 38, 39, 40, 41, 42]
]
obj.kth_element(matrix, 9)
obj.kth_element(matrix, 21)
obj.kth_element(matrix, 42)
end
main()```
```

#### Output

`````` Spiral 9'th Element  : 24
Spiral 21'th Element  : 13
Spiral 42'th Element  : 21``````
``````/*
Scala Program
Print K’th element in spiral form of matrix
*/
class MyMatrix {
def spiral(matrix: Array[Array[Int]], s_row: Int, s_col: Int, e_row: Int, e_col: Int, size: Int): Unit = {
var result: Int = 0;
var k: Int = size;

//Left to right
var i: Int = s_col;
while (i <= e_col && k > 0) {
if (k == 1) {
result = matrix(s_row)(i);
}
i += 1;
k -= 1;
}
//Top to down
i = s_row + 1;
while (i <= e_row && k > 0) {
if (k == 1) {
result = matrix(i)(e_col);
}
i += 1;
k -= 1;
}
//Bottom right to bottom-left
i = e_col - 1;
while (i >= s_col && k > 0) {
if (k == 1) {
result = matrix(e_row)(i);
}
i -= 1;
k -= 1;
}
//Bottom left to top
i = e_row - 1;
while (i > s_row && k > 0) {
if (k == 1) {
result = matrix(i)(s_row);
}
i -= 1;
k -= 1;
}
if (k == 0) {
print(" " + result);
}
if (s_row + 1 <= e_row - 1 && k > 0) {
this.spiral(matrix, s_row + 1, s_col + 1, e_row - 1, e_col - 1, k);
}
}
def kth_element(matrix: Array[Array[Int]], k: Int): Unit = {
val row: Int = matrix.length;
val col: Int = matrix(0).length;

if (k < 0 || k > col * row) {
print("\n Element " + k + " not exist ");
} else {
print("\n Spiral " + k + "'th Element : ");
this.spiral(matrix, 0, 0, row - 1, col - 1, k);
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyMatrix = new MyMatrix();
val matrix: Array[Array[Int]] = Array(
Array(1, 2, 3, 4, 5, 6),
Array(7, 8, 9, 10, 11, 12),
Array(13, 14, 15, 16, 17, 18),
Array(19, 20, 21, 22, 23, 24),
Array(25, 26, 27, 28, 29, 30),
Array(31, 32, 33, 34, 35, 36),
Array(37, 38, 39, 40, 41, 42));
obj.kth_element(matrix, 9);
obj.kth_element(matrix, 21);
obj.kth_element(matrix, 42);
}
}```
```

#### Output

`````` Spiral 9'th Element :  24
Spiral 21'th Element :  13
Spiral 42'th Element :  21``````
``````/*
Swift 4 Program
Print K’th element in spiral form of matrix
*/
class MyMatrix {
func spiral(_ matrix: [
[Int]
], _ s_row: Int, _ s_col: Int, _ e_row: Int, _ e_col: Int, _ size: Int) {
var result: Int = 0;
var k: Int = size;
//Left to right
var i: Int = s_col;
while (i <= e_col && k > 0) {
if (k == 1) {
result = matrix[s_row][i];
}
i += 1;
k -= 1;
}
//Top to down
i = s_row + 1;
while (i <= e_row && k > 0) {
if (k == 1) {
result = matrix[i][e_col];
}
i += 1;
k -= 1;
}
//Bottom right to bottom-left
i = e_col - 1;
while (i >= s_col && k > 0) {
if (k == 1) {
result = matrix[e_row][i];
}
i -= 1;
k -= 1;
}
//Bottom left to top
i = e_row - 1;
while (i > s_row && k > 0) {
if (k == 1) {
result = matrix[i][s_row];
}
i -= 1;
k -= 1;
}
if (k == 0) {
print(" ", result, terminator: "");
}
if (s_row + 1 <= e_row - 1 && k > 0) {
self.spiral(matrix, s_row + 1, s_col + 1, e_row - 1, e_col - 1, k);
}
}
func kth_element(_ matrix: [
[Int]
], _ k: Int) {
let row: Int = matrix.count;
let col: Int = matrix[0].count;
if (k < 0 || k > col * row) {
print("\n Element ", k ," not exist ", terminator: "");
} else {
print("\n Spiral ", k ,"'th Element : ", terminator: "");
self.spiral(matrix, 0, 0, row - 1, col - 1, k);
}
}
}
func main() {
let obj: MyMatrix = MyMatrix();
let matrix: [
[Int]
] = [
[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24],
[25, 26, 27, 28, 29, 30],
[31, 32, 33, 34, 35, 36],
[37, 38, 39, 40, 41, 42]
];
obj.kth_element(matrix, 9);
obj.kth_element(matrix, 21);
obj.kth_element(matrix, 42);
}
main();```
```

#### Output

`````` Spiral  9 'th Element :   24
Spiral  21 'th Element :   13
Spiral  42 'th Element :   21``````

## Output Explanation

The output includes the K'th element of the matrix's spiral traversal for each value of K specified in the code. The calculated K'th elements are printed in sequence.

## Time Complexity

The time complexity of the algorithm is O(N), where N is the number of elements in the matrix. This is because we traverse through each element once in a spiral manner.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post