Toeplitz Matrix


  • 0

    Click here to see the full article post


  • -1
    O

    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


  • 0
    D

    It's so clear once you see the solution.


  • -1
    M

    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;
    }


  • 0
    N

    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;
    }
    }


  • 0

    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))
    

  • 0
    J

    @fuxuemingzhu 。。。


  • 0

    @jinhongliang 2333333 给我点个赞吧


  • 0

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


  • 0
    M

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


  • 1

    @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.


  • 0

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


  • 0
    M

    @StefanPochmann Indeed, thanks for the fast reply!


  • 0

    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;
      };

  • 0
    S
    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.


  • -1
    P

    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;
        
    }
    

    }


  • 0
    B

    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


  • 0
    B
    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
    

  • 0
    M

    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;
    }
    }


  • 0
    C

    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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.