Given a matrix, the task is to convert the given Matrix into sorted Spiral Matrix.
Examples:
Input: y[][] = {
{ 2, 5, 12 },
{ 22, 54, 55 },
{ 1, 6, 8 }
};
Output:
1 2 5
45 55 6
22 12 8
Input: y[][] = {
{ 2, 5, 12 },
{ 22, 45, 55 },
{ 1, 6, 8 },
{ 13, 56, 10 }
};
Output:
1 2 5
45 55 6
22 56 8
13 12 10
Approach:
- Convert the given 2D array into a 1D array.
- Sort the 1D array
- Convert 1D to Spiral matrix
- This can be solved by 4 for loops which store all the elements. Every for loop defines a single direction movement along with the matrix. The first for loop represents the movement from left to right, whereas the second crawl represents the movement from top to bottom, the third represents the movement from the right to left, and the fourth represents the movement from bottom to up.
Below is the implementation of the above approach:
C++
// C++ program to Convert given Matrix// into sorted Spiral Matrix#include <bits/stdc++.h>using namespace std;const int MAX = 1000;// Function to convert the array to Spiralvoid ToSpiral(int m, int n, int Sorted[], int a[MAX][MAX]){ // For Array pointer int index = 0; // k - starting row index // m - ending row index // l - starting column index // n - ending column index int k = 0, l = 0; while (k < m && l < n) { // Print the first row // from the remaining rows for (int i = l; i < n; ++i) { a[k][i] = Sorted[index]; index++; } k++; // Print the last column // from the remaining columns for (int i = k; i < m; ++i) { a[i][n - 1] = Sorted[index]; index++; } n--; // Print the last row // from the remaining rows if (k < m) { for (int i = n - 1; i >= l; --i) { a[m - 1][i] = Sorted[index]; index++; } m--; } // Print the first column // from the remaining columns if (l < n) { for (int i = m - 1; i >= k; --i) { a[i][l] = Sorted[index]; index++; } l++; } }}// Function to convert 2D array to 1D arrayvoid convert2Dto1D(int y[MAX][MAX], int m, int n,int x[]){ int index = 0; // Store value 2D Matrix To 1D array for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { x[index] = y[i][j]; index++; } }}// Function to print the Matrixvoid PrintMatrix(int a[MAX][MAX], int m, int n){ // Print Spiral Matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { cout << a[i][j] << " "; } cout << endl; }}// Function to Convert given Matrix// into sorted Spiral Matrixvoid convertMatrixToSortedSpiral( int y[MAX][MAX], int m, int n){ int a[MAX][MAX] = {0}; int x[m * n]; convert2Dto1D(y, m, n,x); sort(x, x + n * m); ToSpiral(m, n, x, a); PrintMatrix(a, m, n);}// Driver codeint main(){ int m = 4, n = 3; int y[MAX][MAX] = { { 2, 5, 12 }, { 22, 45, 55 }, { 1, 6, 8 }, { 13, 56, 10 }}; convertMatrixToSortedSpiral(y, m, n); return 0;}// This code is contributed by Arnab Kundu |
Java
// Java program to Convert given Matrix// into sorted Spiral Matriximport java.util.*;public class TwistedMatrix { static int MAX = 1000; // Function to convert the array to Spiral static void ToSpiral(int m, int n, int Sorted[], int a[][]) { // For Array pointer int index = 0; // k - starting row index // m - ending row index // l - starting column index // n - ending column index int k = 0, l = 0; while (k < m && l < n) { // Print the first row // from the remaining rows for (int i = l; i < n; ++i) { a[k][i] = Sorted[index]; index++; } k++; // Print the last column // from the remaining columns for (int i = k; i < m; ++i) { a[i][n - 1] = Sorted[index]; index++; } n--; // Print the last row // from the remaining rows if (k < m) { for (int i = n - 1; i >= l; --i) { a[m - 1][i] = Sorted[index]; index++; } m--; } // Print the first column // from the remaining columns if (l < n) { for (int i = m - 1; i >= k; --i) { a[i][l] = Sorted[index]; index++; } l++; } } } // Function to convert 2D array to 1D array public static int[] convert2Dto1D( int y[][], int m, int n) { int index = 0; int x[] = new int[m * n]; // Store value 2D Matrix To 1D array for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { x[index] = y[i][j]; index++; } } return x; } // Function to print the Matrix public static void PrintMatrix( int a[][], int m, int n) { // Print Spiral Matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { System.out.print(a[i][j] + " "); } System.out.println(); } } // Function to sort the array public static int[] SortArray(int x[]) { // Sort array Using InBuilt Function Arrays.sort(x); return x; } // Function to Convert given Matrix // into sorted Spiral Matrix public static void convertMatrixToSortedSpiral( int y[][], int m, int n) { int a[][] = new int[MAX][MAX]; int x[] = new int[m * n]; x = convert2Dto1D(y, m, n); x = SortArray(x); ToSpiral(m, n, x, a); PrintMatrix(a, m, n); } // Driver code public static void main(String[] args) { int m = 4, n = 3; int y[][] = { { 2, 5, 12 }, { 22, 45, 55 }, { 1, 6, 8 }, { 13, 56, 10 } }; convertMatrixToSortedSpiral(y, m, n); }}// This article is contributed by VRUND R PATEL |
Python 3
# Python3 program to Convert given Matrix# into sorted Spiral MatrixMAX = 1000# Function to convert the array to Spiraldef ToSpiral(m, n, Sorted, a): # For Array pointer index = 0 # k - starting row index # m - ending row index # l - starting column index # n - ending column index k = 0 l = 0 while (k < m and l < n): # Print the first row # from the remaining rows for i in range(l, n, 1): a[k][i] = Sorted[index] index += 1 k += 1 # Print the last column # from the remaining columns for i in range(k, m, 1): a[i][n - 1] = Sorted[index] index += 1 n -= 1 # Print the last row # from the remaining rows if (k < m): i = n - 1 while(i >= l): a[m - 1][i] = Sorted[index] index += 1 i -= 1 m -= 1 # Print the first column # from the remaining columns if (l < n): i = m - 1 while(i >= k): a[i][l] = Sorted[index] index += 1 i -= 1 l += 1# Function to convert 2D array to 1D arraydef convert2Dto1D(y, m, n): index = 0 x = [0 for i in range(m * n)] # Store value 2D Matrix To 1D array for i in range(m): for j in range(n): x[index] = y[i][j] index += 1 return x# Function to print the Matrixdef PrintMatrix(a, m, n): # Print Spiral Matrix for i in range(m): for j in range(n): print(a[i][j], end =" ") print('\n', end = "")# Function to sort the arraydef SortArray(x): # Sort array Using InBuilt Function x.sort(reverse = False) return x# Function to Convert given Matrix# into sorted Spiral Matrixdef convertMatrixToSortedSpiral(y, m, n): a = [[0 for i in range(MAX)] for j in range(MAX)] x = [0 for i in range(15)] x = convert2Dto1D(y, m, n) x = SortArray(x) ToSpiral(m, n, x, a) PrintMatrix(a, m, n)# Driver codeif __name__ == '__main__': m = 4 n = 3 y = [[2, 5, 12], [22, 45, 55], [1, 6, 8], [13, 56, 10]] convertMatrixToSortedSpiral(y, m, n)# This code is contributed by Surendra_Gangwar |
C#
// C# program to Convert given Matrix// into sorted Spiral Matrixusing System;class GFG { static int MAX = 1000; // Function to convert the array to Spiral static void ToSpiral(int m, int n, int []Sorted, int [,]a) { // For Array pointer int index = 0; // k - starting row index // m - ending row index // l - starting column index // n - ending column index int k = 0, l = 0; while (k < m && l < n) { // Print the first row // from the remaining rows for (int i = l; i < n; ++i) { a[k, i] = Sorted[index]; index++; } k++; // Print the last column // from the remaining columns for (int i = k; i < m; ++i) { a[i, n - 1] = Sorted[index]; index++; } n--; // Print the last row // from the remaining rows if (k < m) { for (int i = n - 1; i >= l; --i) { a[m - 1, i] = Sorted[index]; index++; } m--; } // Print the first column // from the remaining columns if (l < n) { for (int i = m - 1; i >= k; --i) { a[i, l] = Sorted[index]; index++; } l++; } } } // Function to convert 2D array to 1D array public static int[] convert2Dto1D(int [,]y, int m, int n) { int index = 0; int []x = new int[m * n]; // Store value 2D Matrix To 1D array for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { x[index] = y[i, j]; index++; } } return x; } // Function to print the Matrix public static void PrintMatrix(int [,]a, int m, int n) { // Print Spiral Matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { Console.Write(a[i, j] + " "); } Console.WriteLine(); } } // Function to sort the array public static int[] SortArray(int []x) { // Sort array Using InBuilt Function Array.Sort(x); return x; } // Function to Convert given Matrix // into sorted Spiral Matrix public static void convertMatrixToSortedSpiral(int [,]y, int m, int n) { int [,]a = new int[MAX, MAX]; int []x = new int[m * n]; x = convert2Dto1D(y, m, n); x = SortArray(x); ToSpiral(m, n, x, a); PrintMatrix(a, m, n); } // Driver code public static void Main(String[] args) { int m = 4, n = 3; int [,]y = {{ 2, 5, 12 }, { 22, 45, 55 }, { 1, 6, 8 }, { 13, 56, 10 }}; convertMatrixToSortedSpiral(y, m, n); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to Convert given Matrix// into sorted Spiral Matrixlet MAX = 1000;// Function to convert the array to Spiralfunction ToSpiral(m,n,Sorted,a){ // For Array pointer let index = 0; // k - starting row index // m - ending row index // l - starting column index // n - ending column index let k = 0, l = 0; while (k < m && l < n) { // Print the first row // from the remaining rows for (let i = l; i < n; ++i) { a[k][i] = Sorted[index]; index++; } k++; // Print the last column // from the remaining columns for (let i = k; i < m; ++i) { a[i][n - 1] = Sorted[index]; index++; } n--; // Print the last row // from the remaining rows if (k < m) { for (let i = n - 1; i >= l; --i) { a[m - 1][i] = Sorted[index]; index++; } m--; } // Print the first column // from the remaining columns if (l < n) { for (let i = m - 1; i >= k; --i) { a[i][l] = Sorted[index]; index++; } l++; } }}// Function to convert 2D array to 1D arrayfunction convert2Dto1D(y,m,n){ let index = 0; let x = new Array(m * n); // Store value 2D Matrix To 1D array for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { x[index] = y[i][j]; index++; } } return x;}// Function to print the Matrixfunction PrintMatrix(a,m,n){ // Print Spiral Matrix for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { document.write(a[i][j] + " "); } document.write("<br>"); }}// Function to sort the arrayfunction SortArray(x){ // Sort array Using InBuilt Function x.sort(function(a,b){return a-b;}); return x;} // Function to Convert given Matrix // into sorted Spiral Matrixfunction convertMatrixToSortedSpiral(y,m,n){ let a = new Array(MAX); for(let i=0;i<MAX;i++) a[i]=new Array(MAX); let x = new Array(m * n); x = convert2Dto1D(y, m, n); x = SortArray(x); ToSpiral(m, n, x, a); PrintMatrix(a, m, n);} // Driver codelet m = 4, n = 3;let y = [[ 2, 5, 12 ],[ 22, 45, 55 ],[ 1, 6, 8 ],[ 13, 56, 10 ]];convertMatrixToSortedSpiral(y, m, n);// This code is contributed by avanitrachhadiya2155</script> |
Output:
1 2 5 45 55 6 22 56 8 13 12 10
Time Complexity: O(m*n)
Auxiliary Space: O(m*n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
