Given a 2-D matrix mat[][], the task is to print it in the spiral form.
Examples:
Input: mat[][] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}}
Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Input: mat[][] = {
{1, 2, 3, 4, 5, 6},
{7, 8, 9, 10, 11, 12},
{13, 14, 15, 16, 17, 18}}
Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11
Approach: This problem can be easily solved using direction method. Since we are starting with East direction then always turning right whenever next index is either invalid (out of matrix) or visited earlier. The directions followed will be East -> South -> West -> North -> … starting from mat[0][0] and ending finally when all the elements of the matrix have been traversed.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define R 5#define C 5enum direction { east, west, north, south };// Function to set the new direction on turning// right from the current directionvoid turnright(enum direction& c_direction){ switch (c_direction) { case east: c_direction = south; break; case west: c_direction = north; break; case north: c_direction = east; break; case south: c_direction = west; break; }}// Function to return the next possible cell// indexes with current directionpair<int, int> next(int i, int j, const enum direction& c_direction){ switch (c_direction) { case east: j++; break; case west: j--; break; case north: i--; break; case south: i++; break; } return pair<int, int>(i, j);}// Function that returns true// if arr[i][j] is a valid indexbool isvalid(const int& i, const int& j){ if (i < R && i >= 0 && j >= 0 && j < C) return true; return false;}// Function that returns true if arr[i][j]// has already been visitedbool alreadyVisited(int& i, int& j, int& mini, int& minj, int& maxi, int& maxj){ // If inside the current bounds then // it has not been visited earlier if (i >= mini && i <= maxi && j >= minj && j <= maxj) return false; return true;}// Function to update the constraints of the matrixvoid ConstraintWalls(int& mini, int& minj, int& maxi, int& maxj, direction c_direction){ // Update the constraints according // to the direction switch (c_direction) { case east: mini++; break; case west: maxi--; break; case north: minj++; break; case south: maxj--; break; }}// Function to print the given matrix in the spiral formvoid printspiral(int arr[R][C]){ // To store the count of all the indexes int count = 0; // Starting direction is East enum direction current_direction = east; // Boundary constraints in the matrix int mini = 0, minj = 0, maxi = R - 1, maxj = C - 1; int i = 0, j = 0; // While there are elements remaining while (count < (R * C)) { // Print the current element // and increment the count cout << arr[i][j] << " "; count++; // Next possible cell if direction remains the same pair<int, int> p = next(i, j, current_direction); // If current cell is already visited or is invalid if (!isvalid(p.first, p.second) || alreadyVisited(p.first, p.second, mini, minj, maxi, maxj)) { // If not visited earlier then only change the constraint if (!alreadyVisited(i, j, mini, minj, maxi, maxj)) ConstraintWalls(mini, minj, maxi, maxj, current_direction); // Change the direction turnright(current_direction); // Next indexes with new direction p = next(i, j, current_direction); } // Next row and next column i = p.first; j = p.second; }}// Driver codeint main(){ int arr[R][C]; // Fill the matrix int counter = 1; for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) arr[i][j] = counter++; // Print the spiral form printspiral(arr); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG { static int R = 5; static int C = 5; // Function to set the new direction on turning // right from the current direction public static String turnright(String c_direction) { switch (c_direction) { case "east": return "south"; case "west": return "north"; case "north": return "east"; case "south": return "west"; } // returnin null value to avoid the error return ""; } // Function to return the next possible cell // indexes with current direction public static int[] next(int i, int j, String c_direction) { switch (c_direction) { case ("east"): j++; break; case "west": j--; break; case "north": i--; break; case "south": i++; break; } int[] arr = { i, j }; return arr; } // Function that returns true // if arr[i][j] is a valid index public static boolean isvalid(int i, int j) { if (i < R && i >= 0 && j >= 0 && j < C) return true; return false; } // Function that returns true if arr[i][j] // has already been visited public static boolean alreadyVisited(int i, int j, int mini, int minj, int maxi, int maxj) { // If inside the current bounds then // it has not been visited earlier if (i >= mini && i <= maxi && j >= minj && j <= maxj) return false; return true; } // Function to update the constraints of the matrix public static int[] ConstraintWalls(int mini, int minj, int maxi, int maxj, String c_direction) { // Update the constraints according // to the direction switch (c_direction) { case "east": mini++; break; case "west": maxi--; break; case "north": minj++; break; case "south": maxj--; break; } int[] arr = { mini, minj, maxi, maxj }; return arr; } // Function to print the given matrix in the spiral form public static void printspiral(int[][] arr) { // To store the count of all the indexes int count = 0; // Starting direction is East String current_direction = "east"; // Boundary constraints in the matrix int mini = 0, minj = 0, maxi = R - 1, maxj = C - 1; int i = 0, j = 0; // While there are elements remaining while (count < (R * C)) { // Print the current element // and increment the count System.out.print(arr[i][j] + " "); count += 1; // Next possible cell if direction remains the // same int[] p = next(i, j, current_direction); // If current cell is already visited or is // invalid if (!isvalid(p[0], p[1]) || alreadyVisited(p[0], p[1], mini, minj, maxi, maxj)) { // If not visited earlier then only change // the constraint if (!alreadyVisited(i, j, mini, minj, maxi, maxj)) { int[] store = ConstraintWalls( mini, minj, maxi, maxj, current_direction); mini = store[0]; minj = store[1]; maxi = store[2]; maxj = store[3]; } // Change the direction current_direction = turnright(current_direction); // Next indexes with new direction p = next(i, j, current_direction); } // Next row and next column i = p[0]; j = p[1]; } } public static void main(String[] args) { int[][] arr = new int[R][C]; // Fill the matrix int counter = 1; for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) { arr[i][j] = counter; counter += 1; } // Print the spiral form printspiral(arr); }} |
Python3
# Python 3 implementation of the approachR=5C=5direction = ['east', 'west', 'north', 'south']# Function to set the new direction on turning# right from the current directiondef turnright(c_direction): if c_direction=='east': return 'south' elif c_direction=='west': return 'north' elif c_direction=='north': return 'east' else: return 'west'# Function to return the next possible cell# indexes with current directiondef next(i, j, c_direction): if c_direction=='east': j+=1 elif c_direction=='west': j-=1; elif c_direction=='north': i-=1 else: i+=1 return (i, j)# Function that returns true# if arr[i][j] is a valid indexdef isvalid(i, j): if (i < R and i >= 0 and j >= 0 and j < C): return True return False# Function that returns true if arr[i][j]# has already been visiteddef alreadyVisited(i, j, mini, minj, maxi, maxj): # If inside the current bounds then # it has not been visited earlier if (i >= mini and i <= maxi and j >= minj and j <= maxj): return False return True# Function to update the constraints of the matrixdef ConstraintWalls(mini, minj, maxi, maxj, c_direction): # Update the constraints according # to the direction if c_direction=='east': mini+=1 elif c_direction=='west': maxi-=1 elif c_direction=='north': minj+=1 else: maxj-=1 return mini, minj, maxi, maxj# Function to print the given matrix in the spiral formdef printspiral( arr): # To store the count of all the indexes count = 0 # Starting direction is 'east' current_direction = 'east' # Boundary constraints in the matrix mini = 0; minj = 0; maxi = R - 1; maxj = C - 1 i = 0; j = 0 # While there are elements remaining while (count < (R * C)): # Print the current element # and increment the count print(arr[i][j],end=" ") count+=1 # Next possible cell if direction remains the same p = next(i, j, current_direction) # If current cell is already visited or is invalid if (not isvalid(p[0], p[1]) or alreadyVisited(p[0], p[1], mini, minj, maxi, maxj)): # If not visited earlier then only change the constraint if (not alreadyVisited(i, j, mini, minj, maxi, maxj)): mini, minj, maxi, maxj=ConstraintWalls(mini, minj, maxi, maxj, current_direction) # Change the direction current_direction=turnright(current_direction) # Next indexes with new direction p = next(i, j, current_direction) # Next row and next column i = p[0] j = p[1]# Driver codeif __name__ == '__main__': arr=[[0 for j in range(C)]for i in range(R)] # Fill the matrix counter = 1 for i in range(R): for j in range(C): arr[i][j] = counter counter+=1 # Print the spiral form printspiral(arr) print()# This code is contributed by Amartya Ghosh |
C#
// C# implementation of the approachusing System;using System.Text;public class GFG{ static int R = 5; static int C = 5; // Function to set the new direction on turning // right from the current direction public static string turnright(string c_direction) { switch (c_direction) { case "east": return "south"; case "west": return "north"; case "north": return "east"; case "south": return "west"; } // returnin null value to avoid the error return ""; } // Function to return the next possible cell // indexes with current direction public static int[] next(int i, int j, string c_direction) { switch (c_direction) { case ("east"): j++; break; case "west": j--; break; case "north": i--; break; case "south": i++; break; } int[] arr = { i, j }; return arr; } // Function that returns true // if arr[i][j] is a valid index public static bool isvalid(int i, int j) { if (i < R && i >= 0 && j >= 0 && j < C) return true; return false; } // Function that returns true if arr[i][j] // has already been visited public static bool alreadyVisited(int i, int j, int mini, int minj, int maxi, int maxj) { // If inside the current bounds then // it has not been visited earlier if (i >= mini && i <= maxi && j >= minj && j <= maxj) return false; return true; } // Function to update the constraints of the matrix public static int[] ConstraintWalls(int mini, int minj, int maxi, int maxj, string c_direction) { // Update the constraints according // to the direction switch (c_direction) { case "east": mini++; break; case "west": maxi--; break; case "north": minj++; break; case "south": maxj--; break; } int[] arr = { mini, minj, maxi, maxj }; return arr; } // Function to print the given matrix in the spiral form public static void printspiral(int[,] arr) { // To store the count of all the indexes int count = 0; // Starting direction is East string current_direction = "east"; // Boundary constraints in the matrix int mini = 0, minj = 0, maxi = R - 1, maxj = C - 1; int i = 0, j = 0; // While there are elements remaining while (count < (R * C)) { // Print the current element // and increment the count Console.Write(arr[i,j] + " "); count += 1; // Next possible cell if direction remains the // same int[] p = next(i, j, current_direction); // If current cell is already visited or is // invalid if (!isvalid(p[0], p[1]) || alreadyVisited(p[0], p[1], mini, minj,maxi, maxj)) { // If not visited earlier then only change // the constraint if (!alreadyVisited(i, j, mini, minj, maxi, maxj)) { int[] store = ConstraintWalls(mini, minj, maxi, maxj,current_direction); mini = store[0]; minj = store[1]; maxi = store[2]; maxj = store[3]; } // Change the direction current_direction = turnright(current_direction); // Next indexes with new direction p = next(i, j, current_direction); } // Next row and next column i = p[0]; j = p[1]; } } //Driver Code static public void Main (){ int[,] arr = new int[R,C]; // Fill the matrix int counter = 1; for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) { arr[i,j] = counter; counter += 1; } // Print the spiral form printspiral(arr); }}//This code is contributed by shruti456rawal |
Javascript
// Javascript implementation of the approachvar R = 5;var C = 5;// Function to set the new direction on turning// right from the current directionfunction turnright(c_direction){ switch (c_direction) { case "east": return "south"; case "west": return "north"; case "north": return "east"; case "south": return "west"; } // returnin null value to avoid the error return "";}// Function to return the next possible cell// indexes with current directionfunction next(i, j, c_direction){ switch (c_direction) { case ("east"): j++; break; case "west": j--; break; case "north": i--; break; case "south": i++; break; } var arr = [i,j]; return arr;}// Function that returns true// if arr[i][j] is a valid indexfunction isvalid(i, j){ if (i < R && i >= 0 && j >= 0 && j < C) return true; return false;}// Function that returns true if arr[i][j]// has already been visitedfunction alreadyVisited(i, j, mini, minj, maxi, maxj){ // If inside the current bounds then // it has not been visited earlier if (i >= mini && i <= maxi && j >= minj && j <= maxj) return false; return true;}// Function to update the constraints of the matrixfunction ConstraintWalls(mini, minj, maxi, maxj, c_direction){ // Update the constraints according // to the direction switch (c_direction) { case "east": mini++; break; case "west": maxi--; break; case "north": minj++; break; case "south": maxj--; break; } var store = [mini,minj,maxi,maxj]; return store;}// Function to print the given matrix in the spiral formfunction printspiral(arr){ // To store the count of all the indexes var count = 0; // Starting direction is East var current_direction = "east"; // Boundary constraints in the matrix var mini = 0, minj = 0, maxi = R - 1, maxj = C - 1; var i = 0, j = 0; // string to store the answer var ans = ""; // While there are elements remaining while (count < (R * C)) { // Print the current element // and increment the count ans += arr[i][j] + " "; count += 1; // Next possible cell if direction remains the same var p = next(i, j, current_direction); // If current cell is already visited or is invalid if (!isvalid(p[0], p[1]) || alreadyVisited(p[0], p[1], mini, minj, maxi, maxj)) { // If not visited earlier then only change the constraint if (!alreadyVisited(i, j, mini, minj, maxi, maxj)) { var store = ConstraintWalls(mini, minj, maxi, maxj, current_direction); mini = store[0]; minj = store[1]; maxi = store[2]; maxj = store[3]; } // Change the direction current_direction = turnright(current_direction); // Next indexes with new direction p = next(i, j, current_direction); } // Next row and next column i = p[0]; j = p[1]; } console.log(ans);}// Fill the matrixvar counter = 1;var arr = new Array(R);for (var i = 0; i < R; i++){ arr[i] = new Array(C); for (var j = 0; j < C; j++) { arr[i][j] = counter; counter += 1; }}// Print the spiral formprintspiral(arr); |
Output:
1 2 3 4 5 10 15 20 25 24 23 22 21 16 11 6 7 8 9 14 19 18 17 12 13
Time Complexity: O(R*C)
Space Complexity: O(1), since no extra space has been taken.
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!
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/print-a-given-matrix-in-spiral-form-using-direction-tracking-method/ […]