Find nth elements of spiral matrix

Easy
0/40
Average time to solve is 15m
profile
Contributed by
40 upvotes
Asked in company
Cerence Inc

Problem statement

Given a matrix with ‘N’ rows and ‘M’ columns and an integer ‘K’. Your task is to find the “Kth” element which is obtained while traversing the matrix in spiral form.

Spiral Traversing in the matrix:

The below picture can clearly show how to traverse a matrix in spiral form.

alt text

Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains three space-separated integers ‘N’, ’M’ and ‘K’, where ‘N’ denotes the number of rows in the matrix, ‘M’ denotes the number of columns in the matrix and ‘K’ denotes the position of an element in spiral form matrix.

The next ‘N’ lines for each test case contain the ‘M’ space-separated integer of the “Nth” row of the matrix.
Output Format 
For each test case, return an integer that is present at the “kth” position while traversing the matrix in spiral form.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given functions.
Constraints: 
1 <= T <= 100
1 <= N * M <= 5 * 10^3 
1 <= K  <= N * M
-10^9 <= mat[i][j] <= 10^9


Time limit: 1 second
Sample Input 1:
2
3 4 8
1 2 3 4
5 6 7 8
7 9 2 1
4 4 10
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Sample Output 2:
9
13
Explanation For sample input 1:
Test Case 1:
Given matrix is:

alt text

Spiral form traversal of given matrix is -  
1=> 2=> 3=> 4=> 8=> 1=> 2=> 9=> 7 => 5=> 6 => 7

Hence at the 8'th position element is ‘9’ in spiral form traversal of the given matrix so return the integer ‘9’.

Test Case 2:
Given matrix is

alt text 

Spiral form traversal of given matrix is -  
1=> 2=> 3=> 4=> 8=> 12=> 16=> 15=> 14=> 13=> 9=> 5=> 6=> 7=> 11=>10

Hence at the 10'th position element is ‘13’ in spiral form traversal of the given matrix so return the integer ‘13’.
Sample Input 2:
2
2 3 6
2 3 1
2 1 5
4 2 7
1 2 
3 2
8 3
3 4
Sample Output 2:
2
8
Hint

Traverse the whole matrix in spiral form.

Approaches (2)
Spiral order traversal

The basic idea is to start traversing the matrix in spiral form and find the “k’th” element in the traversal.

 

  • We traverse the matrix in spiral form.
  • Keep two variables ‘startRow = 0’, ‘startCol = 0’, n and m are already ending indices of row and column.
  • Keep a variable ‘count = 0’, if find ‘k == count’ we return.
  • Start iterating ‘i’ from ‘startCol’ to ‘m - 1’. For the first row
    • For any ‘i’ if ‘count == k’, return ‘matrix[startRow][i]’.
  • Update ‘startRow = startRow + 1’.
  • Then iterate ‘i’ from ‘startRow’ to ‘n - 1’. For the last column
    • For any ‘i’ if ‘count == k’, return ‘matrix[i][m - 1]’.
  • Update ‘m = m - 1’.
  • Then iterate ‘i’ from ‘m - 1’ to ‘startCol’ with ‘-1’ jumps. We are iterating the last row from right to left.
    • For any ‘i’ if ‘count == k’, return ‘matrix[n - 1][i]’.
  • Update ‘n = n - 1’
  • Then iterate ‘i’ from ‘n - 1’ to ‘startRow’ with ‘-1’ jumps. We are iterating the first column for a bottom to up
    • For any ‘i’ if ‘count == k’, return ‘matrix[i][startCol]’.
  • Update ‘startCol = startCol + 1’.
  • Increase ‘count’ by ‘1’ in every iteration.
  • Repeat the same step until ‘count’ does not equal the ‘k’.
Time Complexity

O(N * M), Where ‘N’ is the number of rows and ‘M’ is the number of columns.

 

We are iterating every element of the matrix.

Space Complexity

O(1)

 

We are using constant space.

Code Solution
(100% EXP penalty)
Find nth elements of spiral matrix
Full screen
Console