The most simple version:
class Solution { public boolean isToeplitzMatrix(int[][] matrix) { if(matrix==null||matrix[0].length==0) return true; int m = matrix.length, n = matrix[0].length; for(int i=0;i<m-1;i++){ for(int j=0;j<n-1;j++){ if(matrix[i][j] != matrix[i+1][j+1]) return false; } } return true; } }
If want to avoid re-visite the same cells:
class Solution { public boolean isToeplitzMatrix(int[][] matrix) { int m = matrix.length, n = matrix[0].length; for(int k=0;k<n;k++){ int i=0, j=k; while(i<m-1 && j<n-1){ if(matrix[i][j]!=matrix[i+1][j+1]) return false; i++; j++; } } for(int k=1;k<m;k++){ int i=k, j=0; while(i<m-1 && j<n-1){ if(matrix[i][j]!=matrix[i+1][j+1]) return false; i++; j++; } } return true; } }
Follow up 1: load matrix one line by one line
class Solution { public boolean isToeplitzMatrix(int[][] matrix) { if (matrix.length <= 1 || matrix[0].length <= 1) return true; Queue<Integer> q = new LinkedList<>(); for (int i=matrix[0].length-1; i>=0; i--){ //set criteria q.add(matrix[0][i]); } for (int j=1; j<matrix.length; j++){ q.poll(); for (int k=matrix[j].length-1; k>0; k--){ if (matrix[j][k] == q.poll()) // compare q.add(matrix[j][k]); else return false; } q.add(matrix[j][0]); } return true; } }
Follow up 2: load matrix one cell by one one cell
class Solution { // data used for logic - storage complexity O(R + C) HashMap<String, Integer> map = new HashMap<>(); public boolean isToeplitzMatrix(int[][] matrix) { // consider this loop as stream of cell value and position from disk. for (int r = 0; r < matrix.length; r++) { for (int c = 0; c < matrix[0].length; c++) { if (!isToeplitzCell(matrix[r][c], r, c)) { return false; } } } return true; } // We are accessing only one cell value at a time. private boolean isToeplitzCell(int val, int r, int c) { int min = Math.min(r, c); String cell = String.valueOf(r - min) + "," + String.valueOf(c - min); Integer x = map.get(cell); if (x == null) { map.put(cell, val); } else if (x != val) { return false; } return true; } }