Saturday, August 13, 2016

Print K'th element in spiral form of matrix - GeeksforGeeks

Print K'th element in spiral form of matrix - GeeksforGeeks
Given a 2D Matrix of order n X m , print K'th element in spiral form of matrix.

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.
Time Complexity : O(c) where c is number of outer circular rings with respect to k’th element.
Space complexity: O(1)
`int` `findK(``int` `A[MAX][MAX], ``int` `n, ``int` `m, ``int` `k)`
`{`
`    ``if` `(n < 1 || m < 1)`
`        ``return` `-1;`

`    ``/* 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];`

`    ``/* 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));`
`}`

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).