LeetCode 766 - Toeplitz Matrix

https://leetcode.com/problems/toeplitz-matrix/description/

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: True
Explanation:
1234
5123
9512

In the above grid, the diagonals 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.

Example 2:

Input: matrix = [[1,2],[2,2]]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.

Note:

1. matrix will be a 2D array of integers.
2. matrix will have a number of rows and columns in range [1, 20].
3. matrix[i][j] will be integers in range [0, 99].

https://leetcode.com/problems/toeplitz-matrix/solution/
Approach #2: Compare With Top-Left Neighbor [Accepted]

For each diagonal with elements in order $a_1, a_2, a_3, \dots, a_k$, we can check $a_1 = a_2, a_2 = a_3, \dots, a_{k-1} = a_k$. The matrix is Toeplitz if and only if all of these conditions are true for all (top-left to bottom-right) diagonals.

Every element belongs to some diagonal, and it's previous element (if it exists) is it's top-left neighbor. Thus, for the square (r, c), we only need to check r == 0 OR c == 0 OR matrix[r-1][c-1] == matrix[r][c].

For each diagonal with elements in order a1,a2,a3,…,ak$a_1,a_2,a_3,\dots ,a_k$, we can check a1=a2,a2=a3,…,ak−1=ak$a_1=a_2,a_2=a_3,\dots ,a_{k-1}=a_k$. The matrix is Toeplitz if and only if all of these conditions are true for all (top-left to bottom-right) diagonals.

Every element belongs to some diagonal, and it's previous element (if it exists) is it's top-left neighbor. Thus, for the square (r, c), we only need to check r == 0 OR c == 0 OR matrix[r-1][c-1] == matrix[r][c].

    public boolean isToeplitzMatrix(int[][] matrix) {
        for (int r = 0; r < matrix.length; ++r)
            for (int c = 0; c < matrix[0].length; ++c)
                if (r > 0 && c > 0 && matrix[r-1][c-1] != matrix[r][c])
                    return false;
        return true;
    }
https://leetcode.com/problems/toeplitz-matrix/discuss/113422/C%2B%2BJava-Clean-Code

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




public boolean isToeplitzMatrix(int[][] matrix) {

  int row = matrix.length;

  int col = matrix[0].length;

  for (int i = 0; i < row; i++) {

    int ti = i;

    int val = matrix[ti][0];

    for (int j = 0; j < col && ti < row; j++) {

      if (matrix[ti][j] != val)

        return false;

      ti++;

    }

  }

  for (int j = 0; j < col; j++) {

    int tj = j;

    int val = matrix[0][tj];

    for (int i = 0; i < row && tj < col; i++) {

      if (matrix[i][tj] != val)

        return false;

      tj++;

    }

  }

  return true;

}

Approach #1: Group by Category

Intuition and Algorithm

We ask what feature makes two coordinates (r1, c1) and (r2, c2) belong to the same diagonal?

It turns out two coordinates are on the same diagonal if and only if r1 - c1 == r2 - c2.

This leads to the following idea: remember the value of that diagonal as groups[r-c]. If we see a mismatch, the matrix is not Toeplitz; otherwise it is.

  public boolean isToeplitzMatrix(int[][] matrix) {

    Map<Integer, Integer> groups = new HashMap();

    for (int r = 0; r < matrix.length; ++r) {

      for (int c = 0; c < matrix[0].length; ++c) {

        if (!groups.containsKey(r - c))

          groups.put(r - c, matrix[r][c]);

        else if (groups.get(r - c) != matrix[r][c])

          return false;

      }

    }

    return true;

  }

5. Verify if a given matrix is a Toeplitz matrix:
   Follow up, assume that the whole matrix cannot be fit in memory and should be read from a file, assume that a few rows and all columns can be read in, how to verify?

https://leetcode.com/problems/toeplitz-matrix/discuss/147808/Java-Answers-to-the-follow-ups-(load-partial-rowcolumn-one-time)-the-3rd-one-beats-98

the follow-ups (load partial row/column one time)

https://leetcode.com/problems/toeplitz-matrix/discuss/179882/Follow-up-questions
No online judge for the follow-up questions so let's discuss:

1. What if the matrix is stored on disk, and the memory is limited such that you can only load at most one row of the matrix into the memory at once?
Compare half of 1 row with half of the next/previous row.
2. What if the matrix is so large that you can only load up a partial row into the memory at once?
Hash 2 rows (so only 1 element needs to be loaded at a time) and compare the results, excluding the appropriate beginning or ending element.