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
- 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. - 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.
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.
New Comment