Tutorialspoint.dev

Print K’th element in spiral form of matrix

Given a 2D Matrix of order n X m , print K’th element in spiral form of matrix. See the following examples.

Examples:

Input: mat[][] = 
          {{1, 2, 3, 4}
           {5, 6, 7, 8}
           {9, 10, 11, 12}
           {13, 14, 15, 16}}
       k = 6
Output: 12

Input: mat[][] =
       {{1, 2, 3, 4, 5, 6}
        {7, 8, 9, 10, 11, 12}
        {13, 14, 15, 16, 17, 18}}
       k = 17
Output: 10



Simple Solution:
One simple solution is to start traversing matrix in spiral form Print Spiral Matrix and start a counter i.e; count = 0. Whenever count gets equal to K, print that element. Time complexity for this approach will be O(n^2).

Efficient Solution:
We will consider only edge of the matrix at a time and then do recursion for the sub matrix made by removing edges of main matrix.

  1. If k <= m : element is in first row.
  2. Else If k <= (m+n-1) : element is in last column.
  3. Else If k <= (m+n-1+m-1) : element is in last row.
  4. Else If k <= (m+n-1+m-1+n-2) : element is in first column.
  5. Else Element lies somewhere in middle matrix.
// C++ program for Kth element in spiral
// form of matrix
#include<bits/stdc++.h>
#define MAX 100
using namespace std;
  
/* function for Kth element */
int findK(int A[MAX][MAX], int n, int m, int k)
{
    if (n < 1 || m < 1)
        return -1;
  
    /*..........If element is in outermost ring .......*/
    /* Element is in first row */
    if (k <= m)
        return A[0][k-1];
  
    /* Element is in last column */
    if (k <= (m+n-1))
        return A[(k-m)][m-1];
  
    /* Element is in last row */
    if (k <= (m+n-1+m-1))
        return A[n-1][m-1-(k-(m+n-1))];
  
    /* Element is in first column */
    if (k <= (m+n-1+m-1+n-2))
        return A[n-1-(k-(m+n-1+m-1))][0];
  
    /*..........If element is NOT in outermost ring .......*/
    /* Recursion for sub-matrix. &A[1][1] is
       address to next inside sub matrix.*/
    return findK((int (*)[MAX])(&(A[1][1])), n-2,
                  m-2, k-(2*n+2*m-4));
}
  
/* Driver program to test above functions */
int main()
{
    int a[MAX][MAX] = {{1, 2, 3, 4, 5, 6},
                       {7, 8, 9, 10, 11, 12},
                       {13, 14, 15, 16, 17, 18}};
    int k = 17;
    cout << findK(a, 3,6,k) << endl;
    return 0;
}

Output:

 10

Time Complexity : O(c) where c is number of outer circular rings with respect to k’th element.
Space complexity: O(1)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter