What is a Matrix?
A matrix is a two-dimensional array that consists of rows and columns. It is an arrangement of elements in horizontal or vertical lines of entries.
Declaration of Matrix or Grid
The syntax of declaring a Matrix or two-dimensional array is very much similar to that of a one-dimensional array, given as follows.
int arr[number_of_rows][number_of_columns];
However, It produces a data structure that looks like the following:
Representation of matrix
As you can see from the above image, the elements are organized in rows and columns. As shown in the above image the cell x[0][0] is the first element of the first row and first column. The value in the first square bracket represents the row number and the value inside the second square bracket represents the column number. (i.e, x[row][column]).
Initializing Matrix or Grids
There are two methods to initialize two-dimensional arrays.
Method 1
int arr[4][3]={1, 2, 3, 4, 5, 6, 20, 80, 90, 100, 110, 120};
Method 2
int arr[4][3]={{1, 2, 3}, {4, 5, 6}, {20, 80, 90}, {100, 110, 120}};
Here are two methods of initialization of an element during declaration. Here, the second method is preferred because the second method is more readable and understandable so that you can visualize that arr[][] comprises four rows and three columns.
How to access data in Matrix or Grid
Like one-dimensional arrays, matrices can be accessed randomly by using their indices to access the individual elements. A cell has two indices, one for its row number, and the other for its column number. We can use X[i][j] to access the element which is at the ith row and jth column of the matrix.
Matrix
The syntax for access element from the matrix which is at the ith row and jth column:
int value = X[i][j];
How to Print the Elements of a Matrix or Grid:
Printing elements of a matrix or two-dimensional array can be done using two “for” loops.
#include <bits/stdc++.h> using namespace std;
int main()
{ int arr[3][4] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
cout << arr[i][j] << " ";
}
cout << endl;
}
return 0;
} |
/*package whatever //do not write package name here */import java.io.*;
class GFG {
public static void main(String[] args)
{
int[][] arr = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
} // This code is contributed by lokesh |
arr = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12] ]
for i in range(0,3):
for j in range(0,4):
print(arr[i][j],end = " ")
print("")
# This code is contributed by akashish__ |
using System;
public class GFG {
static public void Main()
{
int[, ] arr = new int[3, 4] { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 } };
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 4; j++) {
Console.Write(arr[i, j]);
Console.Write(" ");
}
Console.WriteLine(" ");
}
}
} // This code is contributed by akashish__ |
// JS code for above approach let arr = [[1, 2, 3, 4], [5, 6, 7, 8],
[9, 10, 11, 12]];
for (let i = 0; i < 3; i++) {
let s="";
for (let j = 0; j < 4; j++) {
s+=(arr[i][j]+" ");
}
console.log(s);
} // This code is contributed by ishankhandelwals. |
1 2 3 4 5 6 7 8 9 10 11 12
Some basic problems on Matrix/Grid that you must know:
1. Search in a matrix:
Given a matrix mat[][] of size N x M, where every row and column is sorted in increasing order, and a number X is given. The task is to find whether element X is present in the matrix or not.
Examples:
Input : mat[][] = { {1, 5, 9},
{14, 20, 21},
{30, 34, 43} }
x = 14
Output : YESInput : mat[][] = { {1, 5, 9, 11},
{14, 20, 21, 26},
{30, 34, 43, 50} }
x = 42
Output : NO
Solution:
There are a lot of ways to solve this problem but let’s discuss the idea of a very naive or brute-force approach here.
A Simple Solution is to one by one compare x with every element of the matrix. If matches, then return true. If we reach the end then return false. The time complexity of this solution is O(n x m).
Below is the implementation of the above idea:
#include <bits/stdc++.h> using namespace std;
bool searchInMatrix(vector<vector<int> >& arr, int x)
{ int m = arr.size(), n = arr[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == x)
return true;
}
}
return false;
} // Driver program to test above int main()
{ int x = 8;
vector<vector<int> > arr
= { { 0, 6, 8, 9, 11 },
{ 20, 22, 28, 29, 31 },
{ 36, 38, 50, 61, 63 },
{ 64, 66, 100, 122, 128 } };
if (searchInMatrix(arr, x))
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
} |
// Java code for the above approach import java.io.*;
class GFG {
static boolean searchInMatrix(int[][] arr, int x)
{
int m = arr.length, n = arr[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == x)
return true;
}
}
return false;
}
public static void main(String[] args)
{
int x = 8;
int[][] arr = { { 0, 6, 8, 9, 11 },
{ 20, 22, 28, 29, 31 },
{ 36, 38, 50, 61, 63 },
{ 64, 66, 100, 122, 128 } };
if (searchInMatrix(arr, x)) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
} // This code is contributed by lokeshmvs21. |
# Python code for above approach def searchInMatrix(arr, x):
# m=4,n=5
for i in range(0, 4):
for j in range(0, 5):
if(arr[i][j] == x):
return 1
return
x = 8
arr = [[0, 6, 8, 9, 11],
[20, 22, 28, 29, 31],
[36, 38, 50, 61, 63],
[64, 66, 100, 122, 128]]
if(searchInMatrix(arr, x)):
print("YES")
else:
print("NO")
# This code is contributed by ishankhandelwals.
|
// C# code for the above approach using System;
public class GFG {
static bool searchInMatrix(int[,] arr, int x) {
int m = arr.GetLength(0), n = arr.GetLength(1);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (arr[i, j] == x)
return true;
}
}
return false;
}
public static void Main(string[] args) {
int x = 8;
int[,] arr = { { 0, 6, 8, 9, 11 },
{ 20, 22, 28, 29, 31 },
{ 36, 38, 50, 61, 63 },
{ 64, 66, 100, 122, 128 }
};
if (searchInMatrix(arr, x)) {
Console.WriteLine("YES");
} else {
Console.WriteLine("NO");
}
}
} |
<script> // JavaScript code for the above approach
function searchInMatrix(arr, x) {
let m = arr.length, n = arr[0].length;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (arr[i][j] == x)
return true;
}
}
return false;
}
// Driver program to test above
let x = 8;
let arr
= [[0, 6, 8, 9, 11],
[20, 22, 28, 29, 31],
[36, 38, 50, 61, 63],
[64, 66, 100, 122, 128]];
if (searchInMatrix(arr, x))
document.write("YES" + "<br>");
else
document.write("NO" + "<br>");
// This code is contributed by Potta Lokesh </script>
|
YES
Time Complexity: O(M*N), where M and N are the numbers of rows and columns respectively.
Auxiliary Space: O(1)
2. Program to print the Diagonals of a Matrix
Given a 2D square matrix, print the Principal and Secondary diagonals.
Examples :
Input:
1 2 3 4
4 3 2 1
7 8 9 6
6 5 4 3
Output:
Principal Diagonal: 1, 3, 9, 3
Secondary Diagonal: 4, 2, 8, 6Input:
1 1 1
1 1 1
1 1 1
Output:
Principal Diagonal: 1, 1, 1
Secondary Diagonal: 1, 1, 1
Solution:
The primary diagonal is formed by the elements A00, A11, A22, A33.
Condition for Principal Diagonal: The row-column condition is row = column.The secondary diagonal is formed by the elements A03, A12, A21, A30.
Condition for Secondary Diagonal: The row-column condition is row = numberOfRows – column -1.
// C++ Program to print the Diagonals of a Matrix #include <bits/stdc++.h> using namespace std;
const int MAX = 100;
// Function to print the Principal Diagonal void printPrincipalDiagonal(int mat[][MAX], int n)
{ cout << "Principal Diagonal: ";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Condition for principal diagonal
if (i == j)
cout << mat[i][j] << ", ";
}
}
cout << endl;
} // Function to print the Secondary Diagonal void printSecondaryDiagonal(int mat[][MAX], int n)
{ cout << "Secondary Diagonal: ";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Condition for secondary diagonal
if ((i + j) == (n - 1))
cout << mat[i][j] << ", ";
}
}
cout << endl;
} // Driver code int main()
{ int n = 4;
int a[][MAX] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 } };
printPrincipalDiagonal(a, n);
printSecondaryDiagonal(a, n);
return 0;
} |
// Java Program to print the Diagonals of a Matrix class GFG {
// Function to print the Principal Diagonal
public static void printPrincipalDiagonal(int mat[][], int n) {
System.out.print("Principal Diagonal: ");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Condition for principal diagonal
if (i == j)
System.out.print(mat[i][j] + ", ");
}
}
System.out.print("\n");
}
// Function to print the Secondary Diagonal
public static void printSecondaryDiagonal(int mat[][], int n) {
System.out.print("Secondary Diagonal: ");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Condition for secondary diagonal
if ((i + j) == (n - 1))
System.out.print(mat[i][j] + ", ");
}
}
System.out.print("\n");
}
// Driver Code
public static void main(String[] args) {
int n = 4;
int a[][] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 }
};
printPrincipalDiagonal(a, n);
printSecondaryDiagonal(a, n);
}
} // This code is contributed by ajaymakvana. |
# Python3 Program to print the Diagonals of a Matrix MAX = 100
# Function to print the Principal Diagonal def printPrincipalDiagonal(mat, n):
print("Principal Diagonal: ",end="")
for i in range(0,n):
for j in range(0,n):
# Condition for principal diagonal
if (i == j):
print(mat[i][j] , ", ", end="")
print("")
# Function to print the Secondary Diagonal def printSecondaryDiagonal(mat, n):
print("Secondary Diagonal: ",end = "")
for i in range(0,n):
for j in range(0,n):
# Condition for secondary diagonal
if ((i + j) == (n - 1)):
print(mat[i][j] , ", ", end = "")
print("")
# Driver code n = 4
a = [ [ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ] ]
printPrincipalDiagonal(a, n) printSecondaryDiagonal(a, n) # This code is contributed by akashish__ |
// C# Program to print the Diagonals of a Matrix using System;
namespace ConsoleApp1
{ class Program
{
const int MAX = 100;
// Function to print the Principal Diagonal
static void printPrincipalDiagonal(int[,] mat, int n)
{
Console.Write("Principal Diagonal: ");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// Condition for principal diagonal
if (i == j)
Console.Write(mat[i, j] + ", ");
}
}
Console.WriteLine();
}
// Function to print the Secondary Diagonal
static void printSecondaryDiagonal(int[,] mat, int n)
{
Console.Write("Secondary Diagonal: ");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// Condition for secondary diagonal
if ((i + j) == (n - 1))
Console.Write(mat[i, j] + ", ");
}
}
Console.WriteLine();
}
// Driver code
static void Main(string[] args)
{
int n = 4;
int[,] a = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 1, 2, 3, 4 },
{ 5, 6, 7, 8 } };
printPrincipalDiagonal(a, n);
printSecondaryDiagonal(a, n);
}
}
} // This code is contributed by ishankhandelwals. |
// javascript Program to print the Diagonals of a Matrix // Function to print the Principal Diagonal function printPrincipalDiagonal(mat, n)
{ let s = "";
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// Condition for principal diagonal
if (i == j)
{
s += mat[i][j];
s += " ";
}
}
}
console.log("Principal Diagonal: "+s);
} // Function to print the Secondary Diagonal function printSecondaryDiagonal(mat,n)
{ let s="";
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// Condition for secondary diagonal
if ((i + j) == (n - 1))
{
s += mat[i][j];
s +=" ";
}
}
}
console.log("Secondary Diagonal: "+s);
} // Driver code let n = 4;
let a = [[ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ] ];
printPrincipalDiagonal(a, n);
printSecondaryDiagonal(a, n);
// This code is contributed by garg28harsh.
|
Principal Diagonal: 1, 6, 3, 8, Secondary Diagonal: 4, 7, 2, 5,
Time Complexity: O(n2), As there is a nested loop involved so the time complexity is squared.
Auxiliary Space: O(1).
3. Sort the given matrix:
Given a n x n matrix. The problem is to sort the given matrix in strict order. Here strict order means that the matrix is sorted in a way such that all elements in a row are sorted in increasing order and for row ‘i’, where 1 <= i <= n-1, the first element of row ‘i’ is greater than or equal to the last element of row ‘i-1’.
Examples:
Input : mat[][] = { {5, 4, 7},
{1, 3, 8},
{2, 9, 6} }
Output : 1 2 3
4 5 6
7 8 9
Solution:
The idea to solve this proble is Create a temp[] array of size n^2. Starting with the first row one by one copy the elements of the given matrix into temp[]. Sort temp[]. Now one by one copy the elements of temp[] back to the given matrix.
Below is the implementation:
// C++ implementation to sort the given matrix #include <bits/stdc++.h> using namespace std;
#define SIZE 10 // function to sort the given matrix void sortMat(int mat[SIZE][SIZE], int n)
{ // temporary matrix of size n^2
int temp[n * n];
int k = 0;
// copy the elements of matrix one by one
// into temp[]
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
temp[k++] = mat[i][j];
// sort temp[]
sort(temp, temp + k);
// copy the elements of temp[] one by one
// in mat[][]
k = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
mat[i][j] = temp[k++];
} // function to print the given matrix void printMat(int mat[SIZE][SIZE], int n)
{ for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << mat[i][j] << " ";
cout << endl;
}
} // Driver program to test above int main()
{ int mat[SIZE][SIZE]
= { { 5, 4, 7 }, { 1, 3, 8 }, { 2, 9, 6 } };
int n = 3;
cout << "Original Matrix:\n";
printMat(mat, n);
sortMat(mat, n);
cout << "\nMatrix After Sorting:\n";
printMat(mat, n);
return 0;
} |
// Java implementation to sort the given matrix import java.io.*;
import java.util.*;
class GFG {
static final int SIZE = 10;
// function to sort the given matrix
static void sortMat(int[][] mat, int n)
{
// temporary matrix of size n^2
int[] temp = new int[n * n];
int k = 0;
// copy the elements of matrix one by one
// into temp[]
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
temp[k++] = mat[i][j];
// sort temp[]
Arrays.sort(temp);
// copy the elements of temp[] one by one
// in mat[][]
k = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
mat[i][j] = temp[k++];
}
// function to print the given matrix
static void printMat(int[][] mat, int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
System.out.print(mat[i][j] + " ");
System.out.println();
}
}
public static void main(String[] args)
{
int[][] mat
= { { 5, 4, 7 }, { 1, 3, 8 }, { 2, 9, 6 } };
int n = 3;
System.out.println("Original Matrix:");
printMat(mat, n);
sortMat(mat, n);
System.out.println("\nMatrix After Sorting:");
printMat(mat, n);
}
} // This code is contributed by lokeshmvs21. |
# Python Implementation to sort the given matrix def sortMat(mat, n):
# temporary matrix of size n^2
temp = [0]*n*n
k = 0
# copy the elements of matrix one by one
# leto temp[]
for i in range(0, n):
for j in range(0, n):
temp[k] = mat[i][j]
k += 1
# sort temp[]
temp.sort(reverse = True)
# copy the elements of temp[] one by one
# in mat[][]
k = 0
for i in range(0, n):
for j in range(0, n):
mat[i][j] = temp[k]
k += 1
# function to print the given matrix def printMat(mat, n):
for i in range(0, n):
for j in range(0, n):
print(mat[i][j], end = ' ')
print("")
# Driver program to test above mat = [[5, 4, 7],
[1, 3, 8],
[2, 9, 6]]
n = 3
print("Original Matrix:")
printMat(mat, n) sortMat(mat, n) print("\nMatrix After Sorting:")
printMat(mat, n) # This code is contributed by ishankhandelwals. |
using System;
using System.Linq;
public class GFG{
static readonly int SIZE = 10;
// function to sort the given matrix
static void sortMat(int[,] mat, int n)
{
// temporary matrix of size n^2
int[] temp = new int[n * n];
int k = 0;
// copy the elements of matrix one by one
// into temp[]
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
temp[k++] = mat[i,j];
// sort temp[]
Array.Sort(temp);
// copy the elements of temp[] one by one
// in mat[][]
k = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
mat[i,j] = temp[k++];
}
// function to print the given matrix
static void printMat(int[,] mat, int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
Console.Write(mat[i,j] + " ");
Console.WriteLine();
}
}
static public void Main (){
int[,] mat
= { { 5, 4, 7 }, { 1, 3, 8 }, { 2, 9, 6 } };
int n = 3;
Console.WriteLine("Original Matrix:");
printMat(mat, n);
sortMat(mat, n);
Console.WriteLine("\nMatrix After Sorting:");
printMat(mat, n);
}
} // This code is contributed by akashish__ |
// JS implementation to sort the given matrix // function to sort the given matrix function sortMat(mat, n)
{ // temporary matrix of size n^2
let temp = [];
let k = 0;
// copy the elements of matrix one by one
// leto temp[]
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
temp[k++] = mat[i][j];
// sort temp[]
temp.sort(function (a, b) { return b - a });
// copy the elements of temp[] one by one
// in mat[][]
k = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
mat[i][j] = temp[k++];
} // function to print the given matrix function printMat(mat, n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++)
console.log(mat[i][j]);
}
} // Driver program to test above let mat = [[5, 4, 7], [1, 3, 8], [2, 9, 6]]; let n = 3; console.log("Original Matrix:\n");
printMat(mat, n); sortMat(mat, n); console.log("\nMatrix After Sorting:\n");
printMat(mat, n); // This code is contributed by ishankhandelwals. |
Original Matrix: 5 4 7 1 3 8 2 9 6 Matrix After Sorting: 1 2 3 4 5 6 7 8 9
Time Complexity: O(n2log2n).
Auxiliary Space: O(n2), since n * n extra space has been taken.
4. Rotate a Matrix by 180 degree
Given a square matrix, the task is that turn it by 180 degrees in an anti-clockwise direction without using any extra space.
Examples :
Input : 1 2 3
4 5 6
7 8 9
Output : 9 8 7
6 5 4
3 2 1Input : 1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6
Output : 6 5 4 3
2 1 0 9
8 7 6 5
4 3 2 1
Solution:
There are four steps that are required to solve this problem:
1- Find the transpose of a matrix.
2- Reverse columns of the transpose.
3- Find the transpose of a matrix.
4- Reverse columns of the transpose
Illustration:
Let the given matrix be
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16First we find transpose.
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16Then we reverse elements of every column.
4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13then transpose again
4 3 2 1
8 7 6 5
12 11 10 9
16 15 14 13Then we reverse elements of every column again
16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1
Below is the implementation:
// C++ program for left rotation of matrix by 180 #include <bits/stdc++.h> using namespace std;
#define R 4 #define C 4 // Function to rotate the matrix by 180 degree void reverseColumns(int arr[R][C])
{ for (int i = 0; i < C; i++)
for (int j = 0, k = C - 1; j < k; j++, k--)
swap(arr[j][i], arr[k][i]);
} // Function for transpose of matrix void transpose(int arr[R][C])
{ for (int i = 0; i < R; i++)
for (int j = i; j < C; j++)
swap(arr[i][j], arr[j][i]);
} // Function for display the matrix void printMatrix(int arr[R][C])
{ for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++)
cout << arr[i][j] << " ";
cout << '\n';
}
} // Function to anticlockwise rotate matrix // by 180 degree void rotate180(int arr[R][C])
{ transpose(arr);
reverseColumns(arr);
transpose(arr);
reverseColumns(arr);
} // Driven code int main()
{ int arr[R][C] = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
rotate180(arr);
printMatrix(arr);
return 0;
} |
// Java program for left rotation of matrix by 180 import java.util.*;
class GFG {
public static int R = 4;
public static int C = 4;
// Function to rotate the matrix by 180 degree
public static void reverseColumns(int[][] arr) {
for (int i = 0; i < C; i++)
for (int j = 0, k = C - 1; j < k; j++, k--) {
int temp = arr[j][i];
arr[j][i] = arr[k][i];
arr[k][i] = temp;
}
}
// Function for transpose of matrix
public static void transpose(int[][] arr) {
for (int i = 0; i < R; i++)
for (int j = i; j < C; j++) {
int temp = arr[i][j];
arr[i][j] = arr[j][i];
arr[j][i] = temp;
}
}
// Function for display the matrix
public static void printMatrix(int[][] arr) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++)
System.out.print(arr[i][j] + " ");
System.out.println();
}
}
// Function to anticlockwise rotate matrix by 180 degree
public static void rotate180(int[][] arr) {
transpose(arr);
reverseColumns(arr);
transpose(arr);
reverseColumns(arr);
}
// Driver code
public static void main(String[] args) {
int[][] arr = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 }
};
rotate180(arr);
printMatrix(arr);
}
} |
# Python program for left rotation of matrix by 180 R = 4
C = 4
# Function to rotate the matrix by 180 degree def reverseColumns(arr):
for i in range(C):
for j in range(0, int(C / 2)):
x = arr[j][i]
arr[j][i] = arr[C - 1 - j][i]
arr[C - 1 - j][i] = x
# Function for transpose of matrix def transpose(arr):
for i in range(R):
for j in range(i, C):
x = arr[j][i]
arr[j][i] = arr[i][j]
arr[i][j] = x
# Function for display the matrix def printMatrix(arr):
for i in range(R):
for j in range(C):
print(arr[i][j], end = ' ')
print()
# Function to anticlockwise rotate matrix # by 180 degree def rotate180(arr):
transpose(arr)
reverseColumns(arr)
transpose(arr)
reverseColumns(arr)
# Driven code arr = [[1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ]]
rotate180(arr) printMatrix(arr) # This code is contributed by akashish__ |
// C# code using System;
namespace ConsoleApp1 {
class Program {
const int R = 4;
const int C = 4;
static void Main(string[] args)
{
int[, ] arr = new int[, ] { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
Rotate180(arr);
PrintMatrix(arr);
Console.Read();
}
// Function to rotate the matrix by 180 degree
static void ReverseColumns(int[, ] arr)
{
for (int i = 0; i < C; i++)
for (int j = 0, k = C - 1; j < k; j++, k--)
Swap(ref arr[j, i], ref arr[k, i]);
}
// Function for transpose of matrix
static void Transpose(int[, ] arr)
{
for (int i = 0; i < R; i++)
for (int j = i; j < C; j++)
Swap(ref arr[i, j], ref arr[j, i]);
}
// Function for display the matrix
static void PrintMatrix(int[, ] arr)
{
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++)
Console.Write(arr[i, j] + " ");
Console.WriteLine();
}
}
// Function to anticlockwise rotate matrix
// by 180 degree
static void Rotate180(int[, ] arr)
{
Transpose(arr);
ReverseColumns(arr);
Transpose(arr);
ReverseColumns(arr);
}
// Swap two numbers
static void Swap(ref int a, ref int b)
{
int temp = a;
a = b;
b = temp;
}
}
} |
// Javascript program for left rotation of matrix by 180 let R= 4 let C= 4 // Function to rotate the matrix by 180 degree function reverseColumns(arr)
{ for (let i = 0; i < C; i++)
for (let j = 0, k = C - 1; j < k; j++, k--)
{
let x= arr[j][i];
arr[j][i] = arr[k][i];
arr[k][i]=x;
}
} // Function for transpose of matrix function transpose(arr)
{ for (let i = 0; i < R; i++)
for (let j = i; j < C; j++)
{
let x= arr[j][i];
arr[j][i] = arr[i][j];
arr[i][j]=x;
}
} // Function for display the matrix function printMatrix(arr)
{ document.write(arr);
} // Function to anticlockwise rotate matrix // by 180 degree function rotate180(arr)
{ transpose(arr);
reverseColumns(arr);
transpose(arr);
reverseColumns(arr);
} // Driven code let arr = [[1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ]];
rotate180(arr);
printMatrix(arr);
|
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Time complexity: O(R*C)
Auxiliary Space: O(1)
5. Find unique elements in a matrix
Given a matrix mat[][] having n rows and m columns. We need to find unique elements in the matrix i.e, those elements not repeated in the matrix or those whose frequency is 1.
Examples:
Input : 20 15 30 2
2 3 5 30
6 7 6 8
Output : 3 20 5 7 8 15Input : 1 2 3
5 6 2
1 3 5
6 2 2
Output : No unique element in the matrix
Solution:
The idea is to use hashing and traverse through all the elements of the matrix, If an element is present in the dictionary, then increment its count. Otherwise insert an element with value = 1.
Below is the implementation:
// C++ program to find unique // element in matrix #include <bits/stdc++.h> using namespace std;
#define R 4 #define C 4 // function that calculate unique element int unique(int mat[R][C], int n, int m)
{ int maximum = 0, flag = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
// Find maximum element in
// a matrix
if (maximum < mat[i][j])
maximum = mat[i][j];
// Take 1-D array of (maximum + 1)
// size
int b[maximum + 1] = { 0 };
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++){
int y = mat[i][j];
b[y]++;
}
// print unique element
for (int i = 1; i <= maximum; i++)
if (b[i] == 1)
cout << i << " ";
flag = 1;
if (!flag) {
cout << "No unique element in the matrix";
}
} // Driver program int main()
{ int mat[R][C] = { { 1, 2, 3, 20 },
{ 5, 6, 20, 25 },
{ 1, 3, 5, 6 },
{ 6, 7, 8, 15 } };
// function that calculate unique element
unique(mat, R, C);
return 0;
} // This code is contributed by Naman_Garg. |
// Java program to find unique // element in matrix import java.io.*;
class GFG {
// function that calculate unique element
static void unique(int[][] mat, int n, int m)
{
int maximum = 0, flag = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Find maximum element in
// a matrix
if (maximum < mat[i][j]) {
maximum = mat[i][j];
}
}
}
// Take 1-D array of (maximum + 1)
// size
int[] b = new int[maximum + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int y = mat[i][j];
b[y]++;
}
}
// print unique element
for (int i = 1; i <= maximum; i++) {
if (b[i] == 1) {
System.out.print(i + " ");
}
}
flag = 1;
if (flag == 0) {
System.out.print(
"No unique element in the matrix");
}
}
public static void main(String[] args)
{
int R = 4, C = 4;
int[][] mat = { { 1, 2, 3, 20 },
{ 5, 6, 20, 25 },
{ 1, 3, 5, 6 },
{ 6, 7, 8, 15 } };
// function that calculate unique element
unique(mat, R, C);
}
} // This code is contributed by lokeshmvs21. |
# Python program to find unique # element in matrix # Function that calculate unique element def unique(mat, n, m):
maximum = 0
flag = 0
for i in range(n):
for j in range(m):
# Find maximum element in
# a matrix
if maximum < mat[i][j]:
maximum = mat[i][j]
# Take 1-D array of (maximum + 1)
# size
b = [0] * (maximum + 1)
for i in range(n):
for j in range(m):
y = mat[i][j]
b[y] += 1
# print unique element
for i in range(1, maximum+1):
if b[i] == 1:
print(i, end=' ')
flag = 1
if flag == 0:
print("No unique element in the matrix")
R = 4
C = 4
mat = [[1, 2, 3, 20],
[5, 6, 20, 25],
[1, 3, 5, 6],
[6, 7, 8, 15]]
# function that calculate unique element unique(mat, R, C) # This code is contributed by lokesh. |
// C# program to find unique element in matrix using System;
public class GFG {
// function that calculate unique element
static void unique(int[, ] mat, int n, int m)
{
int maximum = 0, flag = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Find maximum element in
// a matrix
if (maximum < mat[i, j]) {
maximum = mat[i, j];
}
}
}
// Take 1-D array of (maximum + 1)
// size
int[] b = new int[maximum + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int y = mat[i, j];
b[y]++;
}
}
// print unique element
for (int i = 1; i <= maximum; i++) {
if (b[i] == 1) {
Console.Write(i + " ");
}
}
flag = 1;
if (flag == 0) {
Console.Write(
"No unique element in the matrix");
}
}
public static void Main(string[] args)
{
int R = 4, C = 4;
int[, ] mat = { { 1, 2, 3, 20 },
{ 5, 6, 20, 25 },
{ 1, 3, 5, 6 },
{ 6, 7, 8, 15 } };
// function that calculate unique element
unique(mat, R, C);
}
} // This code is contributed by ajaymakavana. |
// JS code let mat = [[1, 2, 3, 20], [5, 6, 20, 25], [1, 3, 5, 6], [6, 7, 8, 15]]; let max = 0; let flag = 0; for (let i = 0; i < mat.length; i++) {
for (let j = 0; j < mat.length; j++) {
if (max < mat[i][j]) {
max = mat[i][j];
}
}
} let b = new Array(max + 1).fill(0);
for (let i = 0; i < mat.length; i++) {
for (let j = 0; j < mat.length; j++) {
let y = mat[i][j];
b[y]++;
}
} for (let i = 1; i <= max; i++) {
if (b[i] == 1) {
console.log(i + " ");
flag = 1;
}
} if (!flag) {
console.log("No unique element in the matrix");
} |
2 7 8 15 25
Time Complexity: O(m*n) where m is the number of rows & n is the number of columns.
Auxiliary Space: O(max(matrix)).
More Practice problems on Matrix/Grid:
Related Article:
- Learn Data Structures and Algorithms | DSA Tutorial
- Why Data Structures and Algorithms Are Important to Learn?
- The Ultimate Beginner’s Guide For DSA
- Introduction to Data Structures
- What is Algorithm | Introduction to Algorithms
- Problems on Matrix Data Structure