Find element in a sorted Matrix

 Given a matrix (two dimensional array) in which each row and each column is sorted, write a method to find an element in it.

Algorithm - start from bottom left element. If element is same then return row & column. If element is more than the given element to be searched, discard the current row. Otherwise discard the current column.

I am also returning total operations performed if element was found.


C/C++ solution



#include <iostream>

using namespace std;

main() {

        int rows, columns;

        cout << "Enter number of rows & columns : "; 
        cin >> rows;
        cin >> columns;

        int mat[rows][columns];

        cout << "Enter matrix elments : ";

        for (int i = 0; i < rows; i++) {
                for(int j = 0; j < columns; j++) {
                        cin >> mat[i][j];
                }   
        }   

        int start_row = 0, end_row = rows - 1, start_col = 0, end_col = columns - 1;

        cout << " Enter element to be searched ";

        int elemToBeSearched;

        cin >> elemToBeSearched;

        int numberOfOperations = 0;

        while (start_col < columns && end_row >=0) {
                numberOfOperations = numberOfOperations + 2; // conditions in while loop
                if (mat[end_row][start_col] == elemToBeSearched) {
                        cout << "element found at row " << end_row + 1 << " column " << start_col + 1 << endl;
                        cout << "total number of operations to find the element in the given matrix " << numberOfOperations << endl;

                       return 0;

                } else if (mat[end_row][start_col] < elemToBeSearched) {

                        start_col++;

                } else {

                        end_row--;

                }

                numberOfOperations += 3; // increment & condition check in above if and else 

        }

        cout << "Element not found " << endl;

}

$ ./a.out 

Enter number of rows & columns : 50 2

Enter matrix elments : 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

 Enter element to be searched 6

element found at row 3 column 2

total number of operations to find the element in the given matrix 242

$ ./a.out 

Enter number of rows & columns : 4 4 

Enter matrix elments : 1 10 15 25 7 12 17 35 13 28 20 39 21 27 49 60

 Enter element to be searched 25

element found at row 1 column 4

total number of operations to find the element in the given matrix 32

$ ./a.out 

Enter number of rows & columns : 10 10

Enter matrix elments : 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

 Enter element to be searched 81

element found at row 9 column 1

Find sub matrix with maximum sum

Suppose you have an NxN matrix of positive and negative integers. Write a code that finds the sub-matrix with the maximum sum of its elements.

or 

Bit less difficult  variant

Given a m * n matrix and value k. Find k * k matrix within the given matrix whose sum is maximum.

Rotate square matrix by 90 degrees

Rotate a square matrix by 90 degrees

Solution in C/C++ - compiler g++


#include <iostream>

using namespace std;

main() {
        int m = 0;

        cout << "Enter number of rows & columns in square matrix " ;

        cin >> m;

        int mat[m][m];

        cout << "Enter elements \n";
        for (int k = 0; k < m; k++) {
                for (int l = 0; l < m; l++) {
                        cin >> mat[k][l];
                }
        }

        for (int j = 0; j < m/2; j++) {
                for (int i = j; i < m - j -1; i++) {
                        int temp1 = 0, temp2 = 0;
                        temp1 = mat[i][m - j - 1];
                        mat[i][m - j - 1] = mat[j][i];
                        temp2 = mat[m - j - 1][m - i - 1];
                        mat[m - j - 1][m - i - 1] = temp1;
                        temp1 = mat[m - i -1][j];
                        mat[m - i -1][j] = temp2;
                        mat[j][i] = temp1;
                }
        }

        cout << "Elements after 90 degree rotation \n";
        for (int k = 0; k < m; k++) {
                for (int l = 0; l < m; l++) {
                        cout << mat[k][l] << " ";

               }

        }

        cout << endl;

}

Execution result:

Enter number of rows & columns in square matrix 4

Enter elements 

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

Elements after 90 degree rotation 

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

Print a square matrix in spiral order

This is what I have written in C/C++


#include <iostream>
using namespace std;

main() {
        int m = 0;

        cout << "Enter number of rows & columns in square matrix " ;

        cin >> m;

        int mat[m][m];

        cout << "Enter elements \n";
        for (int k = 0; k < m; k++) {
                for (int l = 0; l < m; l++) {
                        cin >> mat[k][l];
                }
        }

        for (int j = 0; j < m/2; j++) { // Do it square by square or layer by layer
                for (int i = j; i < m - j -1; i++) {
                        cout << mat[j][i] << " ";
                }
                for (int i = j; i < m - j -1 ; i++) {
                        cout << mat[i][m - j -1] << " ";
                }
                for (int i = j; i < m - j -1; i++) {
                        cout << mat[m - j - 1][m - i - 1] << " ";
                }
                for (int i = j; i < m - j -1; i++) {
                        cout << mat[m - i -1][j] << " ";
                }
                cout << endl;
        }
        if (m % 2 != 0) { // for odd number of rows & columns
                cout << mat[m/2][m/2] << endl;;
        }
}