Given a 3D matrix mat[ ][ ][ ] of size X * Y * Z. The task is to convert this matrix into a fully connected Cyclic linked list. Each node will have the 6 pointers namely: Left, Right, Up, Down, Front, Back.
Examples:
Input: X = 2, Y = 2, Z = 2
mat[0][0][0] = 10 mat[0][0][1] = 11
mat[0][1][0] = 12 mat[0][1][1] = 13
mat[1][0][0] = 14 mat[1][0][1] = 15
mat[1][1][0] = 16 mat[1][1][1] = 17
Output:
element front back left right up down
10 14 14 11 11 12 12
11 15 15 10 10 13 13
12 16 16 13 13 10 10
13 17 17 12 12 11 11
14 10 10 15 15 16 16
15 11 11 14 14 17 17
16 12 12 17 17 14 14
17 13 13 16 16 15 15
Explanation:
For mat[0][0][0] having value 10:
Its back pointer points to cell mat[1][0][0] having value 14.
It doesn’t have any element in front of it. In order to maintain the cyclic order, the front pointer points to cell mat[1][0][0] having value 12.
Its right pointer points to cell mat[0][0][1] having value 11.
It doesn’t have any element to its left. In order to maintain the cyclic order, the left pointer points to cell mat[0][0][1] having value 11.
Its bottom pointer points to cell mat[0][1][0] having value 12.
It doesn’t have any element above it. In order to maintain the cyclic order, the top pointer points to cell mat[0][1][0] having value 12.
In this way, all the pointers of each cell are connected to their respective cells.
Input: X = 1, Y = 3, Z = 2
mat[0][0][0] = 1 mat[0][0][1] = 2 mat[0][0][0] = 3
mat[0][1][0] = 4 mat[0][1][1] = 5 mat[0][0][0] = 6
Output:
element front back left right up down
1 4 4 3 2 1 1
2 5 5 1 3 2 2
3 6 6 2 1 3 3
4 1 1 6 5 4 4
5 2 2 4 6 5 5
6 3 3 5 4 6 6
Approach:
- For each cell of the matrix, create a node consisting of 6 pointers as Up, Down, Left, Right, Back and Front.
- Link the Down pointers of all the nodes. For a given cell, if no cell exists below it, point its down pointer to the topmost cell of the row to maintain the cyclic order.
- Link the Up pointers of all the nodes. For a given cell, if no cell exists above it, point its up pointer to the bottom-most cell of the row to maintain the cyclic order.
- Link the Right pointer of all the nodes. For a given cell, if no cell exists to its right, point its right pointer to the leftmost cell of the row to maintain the cyclic order.
- Link the Left pointer of all the nodes. For a given cell, if no cell exists to its left, point its left pointer to the rightmost cell of the row to maintain the cyclic order.
- Link the Front pointer of all the nodes. For a given cell, if no cell exists in front of it, point its front pointer to the back-most cell of the row to maintain the cyclic order.
- Link the Back pointer of all the nodes. For a given cell, if no cell exists behind it, point its back pointer to the front-most cell of the row to maintain the cyclic order.
- Thus link all the pointers in a cyclic manner. Traverse the entire linked list so formed, and for each node of the linked list, print all the values that it points using its 6 pointers.
Below is the implementation of the above approach:
CPP
// C++ code for the above program#include <bits/stdc++.h>using namespace std;// Node structure of the// 3D-linked listclass ThreeDLinkedListNode {public: int val; ThreeDLinkedListNode* front; ThreeDLinkedListNode* back; ThreeDLinkedListNode* up; ThreeDLinkedListNode* right; ThreeDLinkedListNode* down; ThreeDLinkedListNode* left; ThreeDLinkedListNode( int x, ThreeDLinkedListNode* f = NULL, ThreeDLinkedListNode* b = NULL, ThreeDLinkedListNode* u = NULL, ThreeDLinkedListNode* r = NULL, ThreeDLinkedListNode* d = NULL, ThreeDLinkedListNode* l = NULL) { // initialization of 3D // linkedlist Node val = x; front = f; back = b; up = u; right = r; down = d; left = l; } vector<int> extractNeighbors() { // extracting all front, // back, up, down, left, // right neighbours of // the node vector<int> neighbour; // front back left right up down neighbour.push_back(front->val); neighbour.push_back(back->val); neighbour.push_back(left->val); neighbour.push_back(right->val); neighbour.push_back(up->val); neighbour.push_back(down->val); return neighbour; }};class Solution {public: void setDown( vector<vector<vector<int> > > a, int layer, int row, int column, ThreeDLinkedListNode* node) { // setting the down pointers // of all nodes in a // 3D linked list bool flag = false; ThreeDLinkedListNode* head = node; // loop to traverse the layers for (int i = 0; i < layer; i++) { ThreeDLinkedListNode* start_layer_head = node; // Loop to traverse the // columns of each layer for (int j = 0; j < column; j++) { ThreeDLinkedListNode* start = node; // Loop to traverse // each row for (int k = 0; k < row; k++) { // Check if its the // last cell of the // current row if (k == row - 1) node->down = start; else node->down = new ThreeDLinkedListNode( a[i][k + 1][j]); node = node->down; } // Check if it is the last // element of the current // column if (j == column - 1) { node->right = start_layer_head; // Check if it is the // last element of the // current layer if (i < layer - 1) { start_layer_head->back = new ThreeDLinkedListNode( a[i + 1][0][0]); node = start_layer_head->back; } else { start_layer_head->back = head; node = start_layer_head->back; } } else { node->right = new ThreeDLinkedListNode( a[i][0][j + 1]); node = node->right; } } } } void setUp( vector<vector<vector<int> > > a, int layer, int row, int column, ThreeDLinkedListNode* node) { // setting the up pointers of all // nodes in a 3d linked list ThreeDLinkedListNode* head = node; // loop to traverse the layers for (int i = 0; i < layer; i++) { ThreeDLinkedListNode* start_layer_head = node; // Loop to traverse the // columns for (int j = 0; j < column; j++) { ThreeDLinkedListNode* start = node; // Loop to traverse // the rows for (int k = 0; k < row; k++) { node->down->up = node; node = node->down; } // Check if it is the // last element of // the column if (j == column - 1) { node = start_layer_head->back; } else { node = node->right; } } } } void setRight( vector<vector<vector<int> > > a, int layer, int row, int column, ThreeDLinkedListNode* node) { // setting the Right pointers of // all nodes in a 3d linked list ThreeDLinkedListNode* head = node; // loop to traverse the layers for (int i = 0; i < layer; i++) { ThreeDLinkedListNode* start_layer_head = node; // loop to traverse the // columns for (int j = 0; j < column; j++) { ThreeDLinkedListNode* start = node; // loop to traverse // the rows for (int k = 0; k < row; k++) { node->down->right = node->right->down; node = node->down; } // Check if it is the // last element of the // column if (j == column - 1) { node = start_layer_head->back; } else { node = node->right; } } } } void setLeft( vector<vector<vector<int> > > a, int layer, int row, int column, ThreeDLinkedListNode* node) { // setting the Left pointers of // all nodes in a 3d linked list ThreeDLinkedListNode* head = node; // loop to traverse the layers for (int i = 0; i < layer; i++) { ThreeDLinkedListNode* start_layer_head = node; // loop to traverse the // columns for (int j = 0; j < column; j++) { ThreeDLinkedListNode* start = node; // loop to traverse // the rows` for (int k = 0; k < row; k++) { node->right->left = node; node = node->down; } // Check if it is the // last element of the // column if (j == column - 1) { node = start_layer_head->back; } else { node = node->right; } } } } void setBack( vector<vector<vector<int> > > a, int layer, int row, int column, ThreeDLinkedListNode* node) { // setting the Back pointers of // all nodes in a 3d linked list ThreeDLinkedListNode* head = node; // loop to traverse the layers for (int i = 0; i < layer; i++) { ThreeDLinkedListNode* start_layer_head = node; // loop to traverse the // columns for (int j = 0; j < column; j++) { ThreeDLinkedListNode* start = node; // loop to traverse // the rows for (int k = 0; k < row; k++) { node->down->back = node->back->down; node = node->down; } // Check if it is the // last element of the // column if (j == column - 1) { node = start_layer_head->back; } else { node = node->right; node->back = start->back->right; } } } } void setFront( vector<vector<vector<int> > > a, int layer, int row, int column, ThreeDLinkedListNode* node) { // setting the Front pointers of // all nodes in a 3d linked list ThreeDLinkedListNode* head = node; // loop to traverse the layers for (int i = 0; i < layer; i++) { ThreeDLinkedListNode* start_layer_head = node; // loop to traverse the // columns for (int j = 0; j < column; j++) { ThreeDLinkedListNode* start = node; // loop to traverse // the rows for (int k = 0; k < row; k++) { node->back->front = node; node = node->down; } // Check if it is the // last element of the // column if (j == column - 1) { node = start_layer_head->back; } else { node = node->right; node->back = start->back->right; } } } } ThreeDLinkedListNode* ThreeDimensionalMatrixToLinkedList( vector<vector<vector<int> > > a, int layer, int row, int column) { ThreeDLinkedListNode* head = new ThreeDLinkedListNode( a[0][0][0]); ThreeDLinkedListNode* temp = head; // setting down pointers // of all the nodes setDown(a, layer, row, column, temp); // setting up pointers // of all the nodes setUp(a, layer, row, column, temp); // setting right pointers // of all the nodes setRight(a, layer, row, column, temp); // setting left pointers // of all the nodes setLeft(a, layer, row, column, temp); // setting back pointers // of all the nodes setBack(a, layer, row, column, temp); // setting front pointers // of all the nodes setFront(a, layer, row, column, temp); return head; }};void print_2d_matrix( vector<vector<vector<int> > > mat, ThreeDLinkedListNode* head, int rows, int cols, int layer){ ThreeDLinkedListNode* rest; // loop to traverse // the rows for (int i = 0; i < rows; ++i) { rest = head->down; // loop to traverse // the columns for (int j = 0; j < cols; ++j) { cout << mat[layer][i][j] << "\t"; vector<int> neighbors = head->extractNeighbors(); for (auto ne : neighbors) cout << ne << "\t"; cout << "\n"; head = head->right; } head = rest; }}void printOutput( vector<vector<vector<int> > > mat, ThreeDLinkedListNode* head, int layer, int row, int column){ ThreeDLinkedListNode* rest; // loop to traverse the layers for (int i = 0; i < layer; i++) { rest = head->back; print_2d_matrix(mat, head, row, column, i); head = rest; }}// Driver Codeint main(){ // Initialise the count // of layers, columns and // rows int layer = 3; int row = 3; int column = 3; vector<vector<vector<int> > > mat(layer, vector<vector<int> >( row, vector<int>(column))); mat = { { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }, { { 10, 11, 12 }, { 13, 14, 15 }, { 16, 17, 18 } }, { { 19, 20, 21 }, { 22, 23, 24 }, { 25, 26, 27 } } }; // Function Call to form // the linked list for the // given 3D matrix ThreeDLinkedListNode* head = Solution() .ThreeDimensionalMatrixToLinkedList( mat, layer, row, column); cout << "element\t" << "front\tback\t" << "left\tright\t" << "up\tdown\n"; // Function to print the // linked list elements // and thevalues pointed // by corresponding pointers printOutput(mat, head, layer, row, column); return 0;} |
Output:
element front back left right up down 1 19 10 3 2 7 4 2 20 11 1 3 8 5 3 21 12 2 1 9 6 4 22 13 6 5 1 7 5 23 14 4 6 2 8 6 24 15 5 4 3 9 7 25 16 9 8 4 1 8 26 17 7 9 5 2 9 27 18 8 7 6 3 10 1 19 12 11 16 13 11 2 20 10 12 17 14 12 3 21 11 10 18 15 13 4 22 15 14 10 16 14 5 23 13 15 11 17 15 6 24 14 13 12 18 16 7 25 18 17 13 10 17 8 26 16 18 14 11 18 9 27 17 16 15 12 19 10 1 21 20 25 22 20 11 2 19 21 26 23 21 12 3 20 19 27 24 22 13 4 24 23 19 25 23 14 5 22 24 20 26 24 15 6 23 22 21 27 25 16 7 27 26 22 19 26 17 8 25 27 23 20 27 18 9 26 25 24 21
Time Complexity: O(X * Y * Z), where X, Y, Z are the dimensions of the 3D matrix.
Auxiliary Space: O(X * Y * Z), where X, Y, Z are the dimensions of the 3D matrix.
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!
