{"id":1732,"date":"2018-02-02T20:41:59","date_gmt":"2018-02-03T04:41:59","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1732"},"modified":"2018-02-02T20:45:46","modified_gmt":"2018-02-03T04:45:46","slug":"leetcode-766-toeplitz-matrix","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/difficulty\/easy\/leetcode-766-toeplitz-matrix\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode  766. Toeplitz Matrix"},"content":{"rendered":"<p>A matrix is\u00a0<em>Toeplitz<\/em>\u00a0if every diagonal from top-left to bottom-right has the same element.<\/p>\n<p>Now given an\u00a0<code>M x N<\/code>\u00a0matrix, return\u00a0<code>True<\/code>\u00a0if and only if the matrix is\u00a0<em>Toeplitz<\/em>.<br \/>\n<strong>Example 1:<\/strong><\/p>\n<pre class=\"\">Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]\r\nOutput: True\r\nExplanation:\r\n1234\r\n5123\r\n9512\r\n\r\nIn the above grid, the\u00a0diagonals are \"[9]\", \"[5, 5]\", \"[1, 1, 1]\", \"[2, 2, 2]\", \"[3, 3]\", \"[4]\", and in each diagonal all elements are the same, so the answer is True.\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"\">Input: matrix = [[1,2],[2,2]]\r\nOutput: False\r\nExplanation:\r\nThe diagonal \"[1, 2]\" has different elements.\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>matrix<\/code>\u00a0will be a 2D array of integers.<\/li>\n<li><code>matrix<\/code>\u00a0will have a number of rows and columns in range\u00a0<code>[1, 20]<\/code>.<\/li>\n<li><code>matrix[i][j]<\/code>\u00a0will be integers in range\u00a0<code>[0, 99]<\/code>.<\/li>\n<\/ol>\n<p><strong>Idea:<\/strong><\/p>\n<p>Check m[i][j] with m[i-1][j-1]<\/p>\n<p><strong>Solution: Brute Force<\/strong><\/p>\n<p>Time complexity: O(n*m)<\/p>\n<p>Space complexity: O(1)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 32 ms\r\nclass Solution {\r\npublic:\r\n  bool isToeplitzMatrix(vector&lt;vector&lt;int&gt;&gt;&amp; matrix) {\r\n    for (int i = 1; i &lt; matrix.size(); ++i)\r\n      for (int j = 1; j &lt; matrix[0].size(); ++j)\r\n        if (matrix[i][j] != matrix[i - 1][j - 1]) return false;\r\n    return true;\r\n  }\r\n};<\/pre>\n<p>Java<\/p>\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 29 ms\r\nclass Solution {\r\n  public boolean isToeplitzMatrix(int[][] matrix) {\r\n    for (int i = 1; i &lt; matrix.length; ++i)\r\n      for (int j = 1; j &lt; matrix[0].length; ++j)\r\n        if (matrix[i][j] != matrix[i - 1][j - 1]) return false;\r\n    return true;\r\n  }\r\n}<\/pre>\n<p>Python3<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 99 ms\r\n\"\"\"\r\nclass Solution:\r\n  def isToeplitzMatrix(self, matrix):\r\n    m = len(matrix)\r\n    n = len(matrix[0])\r\n    for i in range(1, m):\r\n      for j in range(1, n):\r\n        if matrix[i][j] != matrix[i - 1][j - 1]: return False\r\n    return True<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A matrix is\u00a0Toeplitz\u00a0if every diagonal from top-left to bottom-right has the same element. Now given an\u00a0M x N\u00a0matrix, return\u00a0True\u00a0if and only if the matrix is\u00a0Toeplitz.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,163],"tags":[216],"class_list":["post-1732","post","type-post","status-publish","format-standard","hentry","category-array","category-easy","tag-matrix","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1732","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=1732"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1732\/revisions"}],"predecessor-version":[{"id":1736,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1732\/revisions\/1736"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1732"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1732"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1732"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}