304 North Cardinal St.
Dorchester Center, MA 02124

# Introduction to Matrix or Grid – Knowledge Construction and Algorithms Tutorial

A Matrix/Grid represents a set of numbers organized in an order of rows and columns. It’s needed to surround the weather of a matrix in parentheses or brackets.

A matrix with 9 components is proven under.

This Matrix [M] has 3 rows and three columns. Every ingredient of matrix [M] may be referred to by its row and column quantity. For instance, a23 = 6.

Introduction to Matrix or Grid – Knowledge Construction and Algorithms Tutorials

## What’s a Matrix?

A matrix is a two-dimensional array that consists of rows and columns. It’s an association of components in horizontal or vertical traces of entries.

Instance:

Matrix

## Declaration of Matrix or Grid

The syntax of declaring a Matrix or two-dimensional array may be very a lot much like that of a one-dimensional array, given as follows.

`int arr[number_of_rows][number_of_columns];   `

Nevertheless, It produces an information construction that appears like the next:

Illustration of matrix

As you’ll be able to see from the above picture, the weather are organized in rows and columns. As proven within the above picture the cell x[0][0] is the primary ingredient of the primary row and first column. The worth within the first sq. bracket represents the row quantity and the worth contained in the second sq. bracket represents the column quantity. (i.e, x[row][column]).

## Initializing Matrix or Grids

There are two strategies to initialize two-dimensional arrays.

Methodology 1

int arr[4][3]={1, 2, 3, 4, 5, 6, 20, 80, 90, 100, 110, 120};

Methodology 2

int arr[4][3]={{1, 2, 3}, {4, 5, 6}, {20, 80, 90}, {100, 110, 120}};

Listed here are two strategies of initialization of a component throughout declaration. Right here, the second technique is most well-liked as a result of the second technique is extra readable and comprehensible so to visualize that arr[][] contains 4 rows and three columns.

## How you can entry knowledge in Matrix or Grid

Like one-dimensional arrays, matrices may be accessed randomly by utilizing their indices to entry the person components. A cell has two indices, one for its row quantity, and the opposite for its column quantity. We are able to use X[i][j] to entry the ingredient which is on the ith row and jth column of the matrix.

The syntax for entry ingredient from the matrix which is on the ith row and jth column:

`int worth = X[i][j];`

## How you can Print the Parts of a Matrix or Grid:

Printing components of a matrix or two-dimensional array may be accomplished utilizing two “for” loops.

## C++

 `#embrace ` `utilizing` `namespace` `std;` ` `  `int` `primary()` `{` ` `  `    ``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;` `}`
Output

```1 2 3 4
5 6 7 8
9 10 11 12
```

## Some fundamental issues on Matrix/Grid that you will need to know:

### 1. Search in a matrix:

Given a matrix mat[][] of dimension N x M, the place each row and column is sorted in growing order, and a quantity X is given. The duty is to seek out whether or not ingredient X is current within the matrix or not.

Examples:

Enter : mat[][] = { {1, 5, 9},
{14, 20, 21},
{30, 34, 43} }
x = 14
Output : YES

Enter : mat[][] = { {1, 5, 9, 11},
{14, 20, 21, 26},
{30, 34, 43, 50} }
x = 42
Output : NO

Resolution:

There are a number of methods to resolve this downside however let’s focus on the concept of a really naive or brute-force method right here.

A Easy Resolution is to one after the other examine x with each ingredient of the matrix. If matches, then return true. If we attain the top then return false. The time complexity of this answer is O(n x m).

Under is the implementation of the above thought:

## C++

 `#embrace ` `utilizing` `namespace` `std;` ` `  `bool` `searchInMatrix(vector >& arr, ``int` `x)` `{` `    ``int` `m = arr.dimension(), n = arr[0].dimension();` ` `  `    ``for` `(``int` `i = 0; i < m; i++) {` `        ``for` `(``int` `j = 0; j < n; j++) {` `            ``if` `(arr[i][j] == x)` `                ``return` `true``;` `        ``}` `    ``}` `    ``return` `false``;` `}` ` `  `int` `primary()` `{` `    ``int` `x = 8;` `    ``vector > 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;` `}`

Time Complexity: O(M*N), the place M and N are the numbers of rows and columns respectively.
Auxiliary Area: O(1)

### 2. Program to print the Diagonals of a Matrix

Given a 2D sq. matrix, print the Principal and Secondary diagonals.

Examples :

Enter:
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, 6

Enter:
1 1 1
1 1 1
1 1 1
Output:
Principal Diagonal: 1, 1, 1
Secondary Diagonal: 1, 1, 1

Resolution:

The first diagonal is fashioned by the weather A00, A11, A22, A33.
Situation for Principal Diagonal: The row-column situation is row = column.

The secondary diagonal is fashioned by the weather A03, A12, A21, A30.
Situation for Secondary Diagonal: The row-column situation is row = numberOfRows – column -1.

## C++

 ` `  `#embrace ` `utilizing` `namespace` `std;` ` `  `const` `int` `MAX = 100;` ` `  `void` `printPrincipalDiagonal(``int` `mat[][MAX], ``int` `n)` `{` `    ``cout << ``"Principal Diagonal: "``;` ` `  `    ``for` `(``int` `i = 0; i < n; i++) {` `        ``for` `(``int` `j = 0; j < n; j++) {` ` `  `            ` `            ``if` `(i == j)` `                ``cout << mat[i][j] << ``", "``;` `        ``}` `    ``}` `    ``cout << endl;` `}` ` `  `void` `printSecondaryDiagonal(``int` `mat[][MAX], ``int` `n)` `{` `    ``cout << ``"Secondary Diagonal: "``;` ` `  `    ``for` `(``int` `i = 0; i < n; i++) {` `        ``for` `(``int` `j = 0; j < n; j++) {` ` `  `            ` `            ``if` `((i + j) == (n - 1))` `                ``cout << mat[i][j] << ``", "``;` `        ``}` `    ``}` `    ``cout << endl;` `}` ` `  `int` `primary()` `{` `    ``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;` `}`
Output

```Principal Diagonal: 1, 6, 3, 8,
Secondary Diagonal: 4, 7, 2, 5,
```

Time Complexity: O(n2), As there’s a nested loop concerned so the time complexity is squared.
Auxiliary Area: O(1).

### 3. Kind the given matrix:

Given a n x n matrix. The issue is to kind the given matrix in strict order. Right here strict order implies that the matrix is sorted in a method such that every one components in a row are sorted in growing order and for row ‘i’, the place 1 <= i <= n-1, the primary ingredient of row ‘i’ is bigger than or equal to the final ingredient of row ‘i-1’.

Examples:

Enter : mat[][] = { {5, 4, 7},
{1, 3, 8},
{2, 9, 6} }
Output : 1 2 3
4 5 6
7 8 9

Resolution:

The concept to resolve this proble is Create a temp[] array of dimension n^2. Beginning with the primary row one after the other copy the weather of the given matrix into temp[]. Kind temp[]. Now one after the other copy the weather of temp[] again to the given matrix.

Under is the implementation:

## C++

 `#embrace ` `utilizing` `namespace` `std;` ` `  `#outline SIZE 10` ` `  `void` `sortMat(``int` `mat[SIZE][SIZE], ``int` `n)` `{` `    ` `    ``int` `temp[n * n];` `    ``int` `ok = 0;` ` `  `    ` `    ` `    ``for` `(``int` `i = 0; i < n; i++)` `        ``for` `(``int` `j = 0; j < n; j++)` `            ``temp[k++] = mat[i][j];` ` `  `    ` `    ``kind(temp, temp + ok);` ` `  `    ` `    ` `    ``ok = 0;` `    ``for` `(``int` `i = 0; i < n; i++)` `        ``for` `(``int` `j = 0; j < n; j++)` `            ``mat[i][j] = temp[k++];` `}` ` `  `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;` `    ``}` `}` ` `  `int` `primary()` `{` `    ``int` `mat[SIZE][SIZE]` `        ``= { { 5, 4, 7 }, { 1, 3, 8 }, { 2, 9, 6 } };` `    ``int` `n = 3;` ` `  `    ``cout << ``"Authentic Matrix:n"``;` `    ``printMat(mat, n);` ` `  `    ``sortMat(mat, n);` ` `  `    ``cout << ``"nMatrix After Sorting:n"``;` `    ``printMat(mat, n);` ` `  `    ``return` `0;` `}`
Output

```Authentic 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 Area: O(n2), since n * n additional area has been taken.

### 4. Rotate a Matrix by 180 diploma

Given a sq. matrix, the duty is that flip it by 180 levels in an anti-clockwise path with out utilizing any additional area.

Examples :

Enter :  1  2  3
4  5  6
7  8  9
Output : 9 8 7
6 5 4
3 2 1

Enter :  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

Resolution:

There are 4 steps which are required to resolve this downside:
1- Discover the transpose of a matrix.
2- Reverse columns of the transpose.
3- Discover 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 16

First we discover transpose.
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

Then we reverse components of each column.
4 8 12 16
3 7 11 15
2 6 10 14
1 5  9 13

then transpose once more
4 3 2 1
8 7 6 5
12 11 10 9
16 15 14 13

Then we reverse components of each column once more
16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1

Under is the implementation:

## C++

 `#embrace ` `utilizing` `namespace` `std;` ` `  `#outline R 4` `#outline C 4` ` `  `void` `reverseColumns(``int` `arr[R][C])` `{` `    ``for` `(``int` `i = 0; i < C; i++)` `        ``for` `(``int` `j = 0, ok = C - 1; j < ok; j++, k--)` `            ``swap(arr[j][i], arr[k][i]);` `}` ` `  `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]);` `}` ` `  `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'``;` `    ``}` `}` ` `  `void` `rotate180(``int` `arr[R][C])` `{` `    ``transpose(arr);` `    ``reverseColumns(arr);` `    ``transpose(arr);` `    ``reverseColumns(arr);` `}` ` `  `int` `primary()` `{` `    ``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;` `}`
Output

```16 15 14 13
12 11 10 9
8 7 6 5
4 3 2 1
```

Time complexity: O(R*C)
Auxiliary Area: O(1)

### 5. Discover distinctive components in a matrix

Given a matrix mat[][] having n rows and m columns. We have to discover distinctive components within the matrix i.e, these components not repeated within the matrix or these whose frequency is 1.

Examples:

Enter :  20  15  30  2
2   3   5   30
6   7   6   8
Output : 3  20  5  7  8  15

Enter :  1  2  3
5  6  2
1  3  5
6  2  2
Output : No distinctive ingredient within the matrix

Resolution:

The concept is to make use of hashing and traverse by means of all the weather of the matrix, If a component is current within the dictionary, then increment its depend. In any other case insert a component with worth = 1.

Under is the implementation:

## C++

 `#embrace ` `utilizing` `namespace` `std;` `#outline R 4` `#outline C 4` ` `  `int` `distinctive(``int` `mat[R][C], ``int` `n, ``int` `m)` `{` `    ``int` `most = 0, flag = 0;` `    ``for` `(``int` `i = 0; i < n; i++)` `        ``for` `(``int` `j = 0; j < m; j++)` `            ` `            ` `            ``if` `(most < mat[i][j])` `                ``most = mat[i][j];` ` `  `    ` `    ` `    ``int` `b[maximum + 1] = { 0 };` `    ``for` `(``int` `i = 0; i < n; i++)` `        ``for` `(``int` `j = 0; j < m; j++)` `            ``b[mat[i][j]]++;` ` `  `    ` `    ``for` `(``int` `i = 1; i <= most; i++)` `        ``if` `(b[i] == 1)` `            ``cout << i << ``" "``;` `    ``flag = 1;` ` `  `    ``if` `(!flag) {` `        ``cout << ``"No distinctive ingredient within the matrix"``;` `    ``}` `}` ` `  `int` `primary()` `{` `    ``int` `mat[R][C] = { { 1, 2, 3, 20 },` `                      ``{ 5, 6, 20, 25 },` `                      ``{ 1, 3, 5, 6 },` `                      ``{ 6, 7, 8, 15 } };` ` `  `    ` `    ``distinctive(mat, R, C);` `    ``return` `0;` `}` ` `

Time Complexity: O(m*n) the place m is the variety of rows & n is the variety of columns.
Auxiliary Area: O(max(matrix)).