Toeplitz Matrix

awice

Click here to see the full article post

oorja

my solution
class Solution:
def isToeplitzMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: bool
"""
if any(matrix[i][j] != matrix[i+1][j+1] for i in range(len(matrix)-1) for j in range(len(matrix[0])- 1)):
return False
else:
return True

david301

It's so clear once you see the solution.

myleet012018

We can skip to iterate row '0' and column '0' elements:

public boolean isToeplitzMatrix(int[][] a) {
for(int i=1; i<a.length; i++){
for(int j=1;j<a[0].length;j++){
if(a[i][j]!=a[i-1][j-1])
return false;
}
}
return true;
}

Naks

Here is the code in C#

public class Solution {
public bool IsToeplitzMatrix(int[,] mat) {
for (int r = 1; r < mat.GetLength(0); r++)
for (int c = 1; c <mat.GetLength(1); c++)
{
if(mat[r,c] != mat[r-1,c-1])
{
return false;
}
}
return true;
}
}

fuxuemingzhu

One line solution

class Solution(object):
    def isToeplitzMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: bool
        """
        return all(matrix[row+1][1:] == matrix[row][:-1] for row in range(len(matrix)-1))

jinhongliang

@fuxuemingzhu 。。。

fuxuemingzhu

@jinhongliang 2333333 给我点个赞吧

fuxuemingzhu

@jinhongliang 看错了哈，我还以为回复的是我对这个题单独发的帖子。。

marirod

Why is the time complexity O(N) instead of O(N^2)?

StefanPochmann

@marirod Should say neither O(N) nor O(N^2) but O(MN), I guess @awice overlooked that M and N are already defined in the problem.

awice

@StefanPochmann Thanks, corrected. Funny because I write the problem statements ;( Though with that definition of N it was correct.

marirod

@StefanPochmann Indeed, thanks for the fast reply!

Nevillealee

Javascript
/**

@param {number[][]} matrix
@return {boolean}
*/
var isToeplitzMatrix = function(matrix) {
for(var r = 1; r < matrix.length; r++) {
for(var c = 1; c < matrix[0].length; c++) {
if(matrix[r][c] != matrix[r-1][c-1]) {
return false;
}
}
}
return true;
};

SherMM

def isToeplitzMatrix(self, matrix):
    """
    :type matrix: List[List[int]]
    :rtype: bool
    """
    r, c = len(matrix), len(matrix[0])
    for i in range(r-1):
        for j in range(c-1):
            if matrix[i+1][j+1] != matrix[i][j]:
                return False
    return True

You only need to iterate to next to last row and column, since single-value items will be Toeplitz.

prakashmanwani

class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
System.out.println(matrix.length);

    int rows = matrix.length;
    int columns = matrix[0].length;
    for (int i=1;i<rows;i++){
        for (int j =1;j<columns;j++){
        if (matrix[i-1][j-1]!=matrix[i][j])return false;
        }
    }
    return true;
    
}

}

boloutare

class Solution: def isToeplitzMatrix(self, matrix): """ :type matrix: List[List[int]] :rtype: bool """ for j in range(1, len(matrix)): if matrix[j-1][:len(matrix[j])-1] != matrix[j][1:]: return False return True

boloutare

class Solution:
    def isToeplitzMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: bool
        """
        for j in range(1, len(matrix)):
            if matrix[j-1][:len(matrix[j])-1] != matrix[j][1:]:
                return False
        return True

Metaphysics

C#
public class Solution {
public bool IsToeplitzMatrix(int[,] matrix) {
int col=matrix.GetLength(1);
for(int i=0;i<matrix.Length-col;i++)
{
if((i+1)%col!=0 && matrix[i/col,i%col]!=matrix[(i+col+1)/col,(i+col+1)%col])
{
return false;
}
}
return true;
}
}

chairco

python

class Solution:
    def isToeplitzMatrix(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: bool
        """
        row = len(matrix[0])
        col = len(matrix)

        candidate = matrix[0]
        for i in range(1, col):
            move = 1
            for j in range(move, row):
                if candidate[j-1] != matrix[i][j]:
                    return False
            candidate = matrix[i]
            move += 1
        return True