Check if a matrix is a Toeplitz or not
Given an N × N matrix, check if it is a Toeplitz matrix or not. A Toeplitz matrix or diagonal-constant matrix is a matrix in which each descending diagonal from left to right is constant.
Category: Matrix
Find the shortest distance of every cell from a landmine inside a maze
Given a maze in the form of a rectangular matrix, filled with either O, X, or M, where O represents an open cell, X represents a blocked cell, and M represents landmines in the maze, find the shortest distance of every open cell in the maze from its nearest mine.
Find maximum value of `M[c][d] – M[a][b]` over all choices of indexes
Given a square matrix of integers, find the maximum value of M[c][d] – M[a][b] over every choice of indexes such that c > a and d > b in a single traversal of the matrix.
Construct a binary tree from an ancestor matrix
Given an N × N ancestor matrix, whose cell (i, j) has the value true if i is the ancestor of j in a binary tree, construct a binary tree from it where binary tree nodes are labeled from 0 to N-1.
Generate a list of possible words from a character matrix
Given an M × N boggle board, find a list of all possible words that can be formed by a sequence of adjacent characters on the board.
Find duplicate rows in a binary matrix
Find duplicate rows present in a given binary matrix by traversing the matrix only once.
Find the shortest route in a device to construct a given string
Given a device having left, right, top, and bottom buttons and an OK button to enter a text from a virtual keypad having alphabets from A–Y arranged in a 5 × 5 grid. Find the shortest route in the device to construct a given string if we start from the top-left position in the keypad.
Collect maximum points in a matrix by satisfying given constraints
Given an M × N matrix where each cell can have a value of 1, 0, or -1, where -1 denotes an unsafe cell, collect the maximum number of ones starting from the first cell and by visiting only safe cells (i.e., 0 or 1).
Count the number of paths in a matrix with a given cost to reach the destination cell
Given an M × N matrix where each cell has a non-negative cost associated with it, count the number of paths to reach the last cell (M-1, N-1) of the matrix from its first cell (0, 0) such that the path has given cost.
Find the longest sequence formed by adjacent numbers in the matrix
Given an N × N matrix where each cell has a distinct value in the 1 to N × N. Find the longest sequence formed by adjacent numbers in the matrix such that for each number, the number on the adjacent neighbor is +1 in its value.
Find minimum cost to reach the last cell of a matrix from its first cell
Given an M × N matrix where each cell has a cost associated with it, find the minimum cost to reach the last cell (M-1, N-1) of the matrix from its first cell (0, 0). We can only move one unit right or one unit down from any cell, i.e., from cell (i, j), we can move to (i, j+1) or (i+1, j).
Matrix Chain Multiplication using Dynamic Programming
Matrix chain multiplication is an optimization problem that to find the most efficient way to multiply a given sequence of matrices. The problem is not actually to perform the multiplications but merely to decide the sequence of the matrix multiplications involved.