Find the size of the largest square submatrix of 1’s present in a binary matrix
Given an M × N binary matrix, find the size of the largest square submatrix of 1’s present.
Category: Matrix
Find maximum sum submatrix present in a matrix
Given an N × N matrix, find the maximum sum submatrix present in it.
Find maximum sum `K × K` submatrix in a given `M × N` matrix
Given an M × N matrix, calculate the maximum sum submatrix of size k × k in it in O(M × N) time.
Calculate the sum of all elements in a submatrix in constant time
Given an M × N matrix and two coordinates (p, q) and (r, s) representing top-left and bottom-right coordinates of a submatrix of it, calculate the sum of all elements present in the submatrix.
Report all occurrences of an element in a row-wise and column-wise sorted matrix in linear time
Given an M × N matrix, which is row-wise and column-wise sorted (with all strictly increasing elements in any row or column), report all occurrences of a given element in it in linear time.
Count negative elements present in the sorted matrix in linear time
Given an M × N matrix, which is row-wise and column-wise sorted, count the total number of negative elements present in it in linear time.
Find the probability that a person is alive after taking `n` steps on an island
An island is in the form of a square matrix, and a person is standing inside the matrix. The person can move one step in any direction (right, left, top, down) in the matrix. Calculate the probability that the person is alive after walking n steps on the island, provided that he dies if he steps outside the matrix.
In-place rotate matrix by 90 degrees in a clockwise direction
Given a square matrix, rotate the matrix by 90 degrees in a clockwise direction. The transformation should be done in-place and in quadratic time.
Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix
Given an M × N binary matrix, replace all occurrences of 0’s by 1’s, which are not completely surrounded by 1’s from all sides (top, left, bottom, right, top-left, top-right, bottom-left, and bottom-right).
Find all paths from the first cell to the last cell of a matrix
Given an M × N matrix, find all paths from the first cell to the last cell. We can only move down or to the right from the current cell.
Print diagonal elements of a matrix having a positive slope
Given an M × N matrix, print all its diagonal elements having a positive slope… The idea is to start from each cell of the first column of the matrix to print / diagonal for the matrix’s upper-left half.
Change all elements of row `i` and column `j` in a matrix to 0 if cell `(i, j)` is 0
Give an M × N matrix consisting of only 0 or 1, change all elements of row i and column j to 0 if cell (i, j) has value 0. Do this without using any extra space for every (i, j) having value 0.