The World is a Matrix

Some interesting programming questions related to Matrices. Firstly, get to know what’s a matrix, inverse of matrix, transpose of matrix.

1.     Input is a matrix of size n x m of 0's and 1's. eg:
1 0 0 1
0 0 1 0
0 0 0 0

If a location has 1; make all the elements of that row and column = 1. eg
1 1 1 1
1 1 1 1
1 0 1 1

Solution should be with Time complexity = O(n*m) and space complexity = O(1)

use the first row to record columns needed to be set as all 1's
use the first column to record rows needed to be set as all 1's

1. scan through the matrix, if (a[x][y]==1) {a[0][y]=1; a[x][0]=1}; time O(m*n)
2. scan through the matrix again, for a[x][y], if (a[0][y]==1 || a[x][0]==1) a[x][y] = 1; time O(m*n)

overall time O(m*n)
auxiliary space O(1)

2. Imagine there is a square matrix with n x n cells. Each cell is either filled with a black pixel or a white pixel. Design an algorithm to find the maximum sub-square such that all four borders are filled with black pixel.
3. Given an n X n array with rows sorted and cols sorted; find the number of negative elements in most efficient way.
4. Each cell of an N x N grid is either a 0 or a 1. You are given two such N x N grids, the initial grid and the final grid. There is a button against each row and each column of the initial N x N grid. Pressing a row-button toggles the values of all the cells in that row, and pressing a column-button toggles the values of all the cells in that column. You are required to find the minimum number of button presses required to transform the grid from the initial configuration to the final configuration, and the buttons that must be pressed in order to make this transformation.
5. You are given a two dimensional array (say 5*5) in which all the rows as well as the columns are sorted. Describe an efficient algorithm to discover if an element is present or not.
6. Give the algorithm to multiply large matrix on system with very less memory which can not hold even one column or one row.
7. Write a program to rotate a matrix by 90 degrees.
8. Write a code to calculate kth power of a matrix of size NxN. You can assume that matrix multiplication is O(n^3).
9. Print a given matrix in a spiral manner.
10. Suppose you have a NxN matrix of positive and negative integers. Find the submatrix with the maximum sum of its elements.
11. Multiply two given matrices.
12. Given a M x N matrix with 0's and 1's, find the largest square matrix consisting on 1's and also find the largest rectangular matrix consisting of 0's