Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Sample Examples
3.1.
Example 1:
3.1.1.
Input
3.1.2.
Output
3.1.3.
Explanation
3.2.
Example 2:
3.2.1.
Input
3.2.2.
Output
3.2.3.
Explanation
4.
Simple Approach
5.
Algorithm
6.
Efficient Approach
7.
Algorithm
8.
Implementation
8.1.
Output
9.
Time Complexity
9.1.
Space Complexity
10.
Frequently Asked Questions
10.1.
What is spiral order in Matrix?
10.2.
How do I print numbers in spiral order?
10.3.
How do you traverse a matrix?
11.
Conclusion
Last Updated: Mar 27, 2024

Print X’th element in the spiral form of a matrix

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this blog, we will learn to solve a multidimensional array problem to Print X’th element in the spiral form of a matrix and its time and space complexities. This blog covers a matrix problem. Matrices are one of the most important and often asked data structures in programming contests and technical interviews. There are various standard matrix problems and techniques.

We will go over the entire problem statement, example application, algorithm and complexities in the following article.

Recommended Topic, Array Implementation of Queue

Also see,  Rabin Karp Algorithm

Problem Statement

The aim is to calculate the X'th element of a 2D Matrix of order n * m in the spiral shape of the matrix, say, x in the matrix, given a matrix of integer values. Print the X'th element of a 2D Matrix of order n X m in the spiral shape of the matrix. Consider the following examples.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Sample Examples

Example 1:

Input

mat[][] =   {{1, 2}
             {3, 4}
             {5, 6}}
 x = 6

Output

3

Explanation

In spiral sequence, the components are 

1, 2, 4, 6, 5, 3 hence the 6th element is 3.

Example 2:

Input

mat[][] =   {{1, 2, 3}
             {4, 5, 6}
             {7, 8, 9}}
               
  x = 7

Output

7

Explanation

In spiral sequence, the components are 

1, 2, 3, 6, 9, 8, 7, 4, 5 hence the 7th element is 7.

Simple Approach

Start traversing the matrix in a spiral shape as one straightforward solution. Print the Spiral Matrix and set the counter to zero. Whenever the count reaches K, print the element. This method will have an O(n2) time complexity.

Algorithm

  • To keep track of the count, set the variable count = 0 to 0.
  • Spiral through the matrix from beginning to end.
  • For every iteration, increase the count by one.
  • If the count equals the value of x, print the element and end the loop.

Efficient Approach

To traverse the array's sides, a loop is utilised of the array as it is traversed in spiral order. So, if it can be determined that the kth element is on the given side, this element may be determined in constant time. This can be done both iteratively and recursively.

Algorithm

  • Spiral or cycle your way through the matrix.
  • So, if the cycle is of size m X n, it can be partitioned into four pieces.
  • The element is in the first row, i.e. x<=m.
  • x <= (m+n-1) is the element in the last column.
  • x <= (m+n-1+m-1) is the element in the last row.
  • The element x <= (m+n-1+m-1+n-2) is in the first column.
  • The xth element can be found in constant time if any of the above conditions are met.
  • Otherwise, remove the cycle from the array and call the procedure recursively.

Implementation

/* C++ program to count frequency of k in a matrix of size n where matrix(i, j) = i+j*/
#include <bits/stdc++.h>
#define ll long long
#define vll vector<long long int>
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define endl "\n"
#define vpi vector<pair<ll,ll>>
#define fi first
#define se second
#define pqi priority_queue<ll,vll,greater<ll>>
#define all(x) x.begin(),x.end()
#define py cout << "YES\n"
#define pn cout << "NO\n"
#define MAX 1000
using namespace std;

/* function to find the Kth element */
int find(ll V[MAX][MAX], ll n, ll m, ll x)
{
    if (n < 1 || m < 1)
        return -1;
 
    /* First row element */
    if (x <= m)
        return V[0][x - 1];
 
    /* Last column element */
    if (x <= (m + n - 1))
        return V[(x - m)][m - 1];
 
    /* Last row element */
    if (x <= (m + n - 1 + m - 1))
        return V[n - 1][m - 1 - (x - (m + n - 1))];
 
    /* First column element */
    if (x <= (m + n - 1 + m - 1 + n - 2))
        return V[n - 1 - (x - (m + n - 1 + m - 1))][0];
 
    /* For a sub-matrix, recursion is used. &A[1][1] &A[1][1] &A[1][1]
Inside the sub matrix, the address to the next sub matrix is*/
    return find((ll(*)[MAX])(&(V[1][1])), n - 2,
                 m - 2, x - (2 * n + 2 * m - 4));
}
 
/* Driver code */
int main()
{
    ll a[MAX][MAX] = { { 1, 2, 3, 4, 5},
                        { 6, 7, 8, 9, 10},
                        { 11, 12, 13, 14, 15} };
    ll x = 10;
    cout << find(a, 3, 5, x) << endl;
    return 0;
}

Output

Time Complexity

O(c), where c denotes the number of outer circular rings in relation to the kth element.

Space Complexity

Because constant space is required, the answer is O(1). 

Check out this problem - Matrix Median

Frequently Asked Questions

What is spiral order in Matrix?

The Spiral Matrix problem takes a 2-Dimensional array with N rows and M columns as input and outputs the elements in spiral order. The spiral starts at the top left corner of the input matrix and prints all of the items it encounters as it loops clockwise towards the centre.

How do I print numbers in spiral order?

From row index k to m, print the right column, i.e. the last column or n-1st column, and reduce the count of n. If k m, display the components of the m-1st row from column n-1 to l and decrease the count of m.

How do you traverse a matrix?

Row-major-order and column-major-order are two common methods for traversing a matrix. When a matrix is accessed row by row, it is said to be in row-major order. When a matrix is accessed column by column, it is called column-major order. Recommended: Before proceeding to the solution, please test your method in IDE.

Conclusion

In this blog, we have extensively discussed a multidimensional array problem to Print X’th element in the spiral form of a matrix and its time and space complexities. We hope that this article has helped all of you with additional information about the Data Structures and algorithms. And to learn in-depth about Multi-dimensional Arrays, check out the course on our Arrays on the Coding Ninjas website. Also, take a look at the Coding Ninjas website for some great information, Android DevelopmentCoding Ninjas Studio ProblemsCoding Ninjas Studio Interview BundleCoding Ninjas Studio Interview ExperiencesCoding Ninjas CoursesCoding Ninjas Studio Contests, and Coding Ninjas Studio Test Series. Do upvote our blog in helping other ninjas grow.

Delighted Programming!

Previous article
Program to Check Idempotent Matrix
Next article
Row-wise vs Column-wise Traversal of a Matrix
Live masterclass