Given two values M and N, fill a matrix of size ‘M*N’ in a spiral (or circular) fashion (clockwise) with given array elements.
Examples:
Input: M = 4, N = 4, arr = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16]
Output: 1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7Input: M = 3, N = 4, arr =[1 8 6 3 8 6 1 6 3 2 5 3]
Output: 1 8 6 3
2 5 3 8
3 6 1 6
Approach: The above problem can be solved using matrix traversal with special condition of turn.
The idea is to traverse the matrix in a direction and insert elements level by level, till a boundary or already filled cell is reached. As soon as such a wall is hit, make a right turn and continue the same.
Follow the below steps
- Create a matrix of size m*n with value 0 in each cell initially
- We will traverse a single loop from 1 to m*n
- The direction of movement will be decided by a variable dir with 4 states:
- 0 for Right,
- 1 for Down,
- 2 for Left, and
- 3 for Up
- The current cell of matrix is accessed using i and j as mat[i][j]
- For each direction, the changes in i and j will be:
i j
R: 0, 1
D: 1, 0
L: 0, -1
U: -1, 0
- In each iteration:
- Fill the mat[i][j] with value at current index of array, and increment current index by 1
- Then check if the next step is out of bounds or a non-0 value which means already filled cell
- If the above condition is true, change direction by 1 state
- Shift the i and j pointer as per current direction
C++
// C++ program to fill a matrix with values// from given array in spiral fashion.#include <bits/stdc++.h>using namespace std;// Function to check if the current// traversing pointer has gone out of boundbool outOfBound(int i, int n){ if (i < 0 || i >= n) return true; else return false;}// Function to generate// m*n circular matrixvector<vector<int> > spiralFill( vector<int>& arr, int m, int n){ vector<vector<int> > mat( n, vector<int>(n, 0)); // Direction: R D L U // dir: 0 1 2 3 int dir = 0; // Values to be filled // from arr.begin to arr.end int value = 0, end = arr.size(); // i j // R: 0, 1 // D: 1, 0 // L: 0, -1 // U: -1, 0 vector<vector<int> > dirArr; dirArr.push_back({ 0, 1 }); dirArr.push_back({ 1, 0 }); dirArr.push_back({ 0, -1 }); dirArr.push_back({ -1, 0 }); // Traversal pointers int i = 0, j = 0; while (value < end) { // Fill value mat[i][j] = arr[value]; // Increment curr value value++; // Make a turn if next step // is boundary or a non-0 cell if (outOfBound(i + dirArr[dir][0], m) || outOfBound(j + dirArr[dir][1], n) || mat[i + dirArr[dir][0]] [j + dirArr[dir][1]] != 0) { dir = (dir + 1) % 4; } // Position of next cell i = i + dirArr[dir][0]; j = j + dirArr[dir][1]; } return mat;}// Driver program to test above functionsint main(){ int m = 3, n = 4; vector<int> arr = { 1, 8, 6, 3, 8, 6, 1, 6, 3, 2, 5, 3 }; vector<vector<int> > mat = spiralFill(arr, m, n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) cout << mat[i][j] << " "; cout << endl; } return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Function to check if the current // traversing pointer has gone out of bound static boolean outOfBound(int i, int n) { if (i < 0 || i >= n) return true; else return false; } // Function to generate // m*n circular matrix static int[][] spiralFill(int[] arr, int m, int n) { int[][] mat = new int[n][n]; for (int a = 0; a < n; a++) { for (int b = 0; b < n; b++) { mat[a][b] = 0; } } // Direction: R D L U // dir: 0 1 2 3 int dir = 0; // Values to be filled // from arr.begin to arr.end int value = 0, end = arr.length; // i j // R: 0, 1 // D: 1, 0 // L: 0, -1 // U: -1, 0 int[][] dirArr = new int[4][ 2]; dirArr[0][ 0] = 0; dirArr[0][1] = 1; dirArr[1][0] = 1; dirArr[1][1] = 0; dirArr[2][ 0] = 0; dirArr[2][1] = -1; dirArr[3][0] = -1; dirArr[3][1] = 0; // Traversal pointers int i = 0, j = 0; while (value < end) { // Fill value mat[i][ j] = arr[value]; // Increment curr value value++; // Make a turn if next step // is boundary or a non-0 cell if (outOfBound(i + dirArr[dir][0], m) || outOfBound(j + dirArr[dir][1], n) || mat[i + dirArr[dir][0]] [j + dirArr[dir][ 1]] != 0) { dir = (dir + 1) % 4; } // Position of next cell i = i + dirArr[dir][ 0]; j = j + dirArr[dir][1]; } return mat; } // Driver program to test above functions public static void main (String[] args) { int m = 3, n = 4; int[] arr = { 1, 8, 6, 3, 8, 6, 1, 6, 3, 2, 5, 3 }; int[][] mat = spiralFill(arr, m, n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { System.out.print(mat[i][ j] + " "); } System.out.println(); } }}// This code is contributed by Potta Lokesh |
Python3
# Python program to fill a matrix with values# from given array in spiral fashion.# Function to check if the current# traversing pointer has gone out of bounddef outOfBound(i, n): if (i < 0 or i >= n): return True else: return False# Function to generate# m*n circular matrixdef spiralFill(arr, m, n): mat = [[0 for col in range(n)]for row in range(n)] # Direction: R D L U # dir: 0 1 2 3 dir = 0 # Values to be filled # from arr.begin to arr.end value,end = 0,len(arr) # i j # R: 0, 1 # D: 1, 0 # L: 0, -1 # U: -1, 0 dirArr = [] dirArr.append([0, 1]) dirArr.append([1, 0]) dirArr.append([0, -1]) dirArr.append([-1, 0]) # Traversal pointers i,j = 0,0 while (value < end): # Fill value mat[i][j] = arr[value] # Increment curr value value += 1 # Make a turn if next step # is boundary or a non-0 cell if (outOfBound(i + dirArr[dir][0], m) or outOfBound(j + dirArr[dir][1], n) or mat[i + dirArr[dir][0]][j + dirArr[dir][1]]!= 0): dir = (dir + 1) % 4 # Position of next cell i = i + dirArr[dir][0] j = j + dirArr[dir][1] return mat# Driver program to test above functionsm,n = 3,4arr = [1, 8, 6, 3, 8, 6, 1, 6, 3, 2, 5, 3]mat = spiralFill(arr, m, n)for i in range(m): for j in range(n): print(mat[i][j],end=" ") print()# This code is contributed by shinjanpatra |
C#
// C# program to fill a matrix with values// from given array in spiral fashion.using System;class GFG { // Function to check if the current // traversing pointer has gone out of bound static bool outOfBound(int i, int n) { if (i < 0 || i >= n) return true; else return false; } // Function to generate // m*n circular matrix static int[, ] spiralFill(int[] arr, int m, int n) { int[, ] mat = new int[n, n]; for (int a = 0; a < n; a++) { for (int b = 0; b < n; b++) { mat[a, b] = 0; } } // Direction: R D L U // dir: 0 1 2 3 int dir = 0; // Values to be filled // from arr.begin to arr.end int value = 0, end = arr.Length; // i j // R: 0, 1 // D: 1, 0 // L: 0, -1 // U: -1, 0 int[, ] dirArr = new int[4, 2]; dirArr[0, 0] = 0; dirArr[0, 1] = 1; dirArr[1, 0] = 1; dirArr[1, 1] = 0; dirArr[2, 0] = 0; dirArr[2, 1] = -1; dirArr[3, 0] = -1; dirArr[3, 1] = 0; // Traversal pointers int i = 0, j = 0; while (value < end) { // Fill value mat[i, j] = arr[value]; // Increment curr value value++; // Make a turn if next step // is boundary or a non-0 cell if (outOfBound(i + dirArr[dir, 0], m) || outOfBound(j + dirArr[dir, 1], n) || mat[i + dirArr[dir, 0], j + dirArr[dir, 1]] != 0) { dir = (dir + 1) % 4; } // Position of next cell i = i + dirArr[dir, 0]; j = j + dirArr[dir, 1]; } return mat; } // Driver program to test above functions public static void Main() { int m = 3, n = 4; int[] arr = { 1, 8, 6, 3, 8, 6, 1, 6, 3, 2, 5, 3 }; int[, ] mat = spiralFill(arr, m, n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { Console.Write(mat[i, j] + " "); } Console.WriteLine(); } }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program to fill a matrix with values // from given array in spiral fashion. // Function to check if the current // traversing pointer has gone out of bound const outOfBound = (i, n) => { if (i < 0 || i >= n) return true; else return false; } // Function to generate // m*n circular matrix const spiralFill = (arr, m, n) => { let mat = new Array(n).fill(0).map(() => new Array(n).fill(0)); // Direction: R D L U // dir: 0 1 2 3 let dir = 0; // Values to be filled // from arr.begin to arr.end let value = 0, end = arr.length; // i j // R: 0, 1 // D: 1, 0 // L: 0, -1 // U: -1, 0 let dirArr = []; dirArr.push([0, 1]); dirArr.push([1, 0]); dirArr.push([0, -1]); dirArr.push([-1, 0]); // Traversal pointers let i = 0, j = 0; while (value < end) { // Fill value mat[i][j] = arr[value]; // Increment curr value value++; // Make a turn if next step // is boundary or a non-0 cell if (outOfBound(i + dirArr[dir][0], m) || outOfBound(j + dirArr[dir][1], n) || mat[i + dirArr[dir][0]] [j + dirArr[dir][1]] != 0) { dir = (dir + 1) % 4; } // Position of next cell i = i + dirArr[dir][0]; j = j + dirArr[dir][1]; } return mat; } // Driver program to test above functions let m = 3, n = 4; let arr = [1, 8, 6, 3, 8, 6, 1, 6, 3, 2, 5, 3]; let mat = spiralFill(arr, m, n); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) document.write(`${mat[i][j]} `); document.write("<br/>"); }// This code is contributed by rakeshsahni</script> |
Output
1 8 6 3 2 5 3 8 3 6 1 6
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
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!
