This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is the 766. Toplitz matrix on LeetCode, and the difficulty is simple.

Tag: “Simulation”

I give you an m x N matrix matrix. Returns true if the matrix is a Toplitz matrix; Otherwise, return false.

A matrix is a Toplitz matrix if every diagonal from top left to bottom right has the same elements.

Example 1:

Input: matrix = [[1, 2, 3, 4], [5,1,2,3], [9 *]] output: true explanation: in the matrix, the diagonal is: "[9], [5, 5]", "[1, 1, 1], [2, 2, 2], [3, 3], [4]. All elements on each diagonal are the same, so the answer is True.Copy the code

Example 2:

Input: matrix = [[1,2],[2,2]] Output: false Explanation: elements on diagonal "[1, 2]" are different.Copy the code

Tip:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 20
  • 0 <= matrix[i][j] <= 99

Advanced:

  • What if the matrix is stored on disk and memory is so limited that only one row of the matrix can be loaded into memory at a time?
  • What if the matrix is so large that only an incomplete row can be loaded into memory at a time?

Press “grid” to traverse

For a qualified Toplitz matrix, each cell is always equal to its upper-left cell (if any).

We traverse in units of “grid”, checking each time against the upper-left grid.

In this way, every time we judge a cell, we have to read the values of two cells in the matrix (i.e. non-edge cells will actually be read twice).

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(matrix[i][j] ! = matrix[i -1][j - 1]) return false; }}return true; }}Copy the code
  • Time complexity: O(n∗m)O(n * m)O(n∗m)
  • Space complexity: O(1)O(1)O(1)

Press “Line” to traverse

How about making it a little harder: limiting each grid to being read only once?

At this time we can also check in accordance with the “line” as a unit.

When one full slash is equal, we check the next slash.

Thus, for each cell, we read strictly once (if the entire matrix was on disk, and the operating system’s page-by-page read-by-page mechanisms were not taken into account, the IO cost would be halved).

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int row = m, col = n;
        while (col-- > 0) {
            for (int i = 0, j = col, val = matrix[i++][j++]; i < m && j < n; i++, j++) {
                if(matrix[i][j] ! = val)return false; }}while (row-- > 0) {
            for (int i = row, j = 0, val = matrix[i++][j++]; i < m && j < n; i++, j++) {
                if(matrix[i][j] ! = val)return false; }}return true; }}Copy the code
  • Time complexity: O(n∗m)O(n * m)O(n∗m)
  • Space complexity: O(1)O(1)O(1)

The advanced

  1. What if the matrix is stored on disk and memory is so limited that only one row of the matrix can be loaded into memory at a time?

Using the one-dimensional optimization idea of the “knapsack problem”, suppose we have memory the size of a row, and each time we read a new row we overwrite it “from right to left”, each overwrite being compared to the previous position (i.e., the upper-left position of the previous row).

As shown in figure:

If you’re interested in more on the backpack problem, check out my summary: An in-depth look at the backpack problem

  1. What if the matrix is so large that only an incomplete row can be loaded into memory at a time?

Pro, this suggestion to upgrade memory, ah bah… Solve the problem as a sub-problem: adjust the way the read matrix is read (read in the vertical direction); Or use additional data to record the number of rows/columns of the current segment. A more logical solution would be to store as an “array” (row storage) and then read directly from the “upper left” or “lower right” values by calculating the offset.

The last

This is the No.761 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.