Toeplitz Matrix

Easy
277.

Toeplitz Matrix

Toeplitz Matrix is an easy coding problem on arrays and matrix, asked in Amazon, Google and Meta interviews.

A matrix is Toeplitz if every diagonal running from top-left to bottom-right holds the same value throughout.

Given an m × n matrix, return true if it is Toeplitz.

Example 1

Input
matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output
true
Explanation
Each descending diagonal is constant.

Example 2

Input
matrix = [[1,2],[2,2]]
Output
false
Explanation
The diagonal starting at (0,0) holds 1 then 2.

Example 3

Input
matrix = [[7]]
Output
true

Constraints

  • 1 <= matrix.length, matrix[i].length <= 8
  • 0 <= matrix[i][j] <= 20

Follow-up: What if the matrix is too large to load into memory at once, and you can only read one row at a time?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @return {boolean}
 */
var isToeplitzMatrix = function(matrix) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Toeplitz Matrix — Solution in Python, Java & C++

Toeplitz Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and matrix.

Toeplitz Matrix is an easy coding problem on arrays and matrix, asked in Amazon, Google and Meta interviews.

  • Difficulty: Easy
  • Topics: Arrays, Matrix
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A matrix is Toeplitz if every diagonal running from top-left to bottom-right holds the same value throughout.

Given an m × n matrix, return true if it is Toeplitz.

Example 1

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation: Each descending diagonal is constant.

Example 2

Input: matrix = [[1,2],[2,2]]
Output: false
Explanation: The diagonal starting at (0,0) holds 1 then 2.

Example 3

Input: matrix = [[7]]
Output: true

Constraints

  • 1 <= matrix.length, matrix[i].length <= 8
  • 0 <= matrix[i][j] <= 20

Follow-up: What if the matrix is too large to load into memory at once, and you can only read one row at a time?

Hints for Toeplitz Matrix

  1. Hint 1

    You never need to walk a whole diagonal — comparing each cell with its up-left neighbour covers every diagonal.

  2. Hint 2

    Start the loops at row 1 and column 1 so the neighbour always exists.

How to solve Toeplitz Matrix

Every diagonal is constant exactly when every cell equals its up-left neighbour.

Approach

  1. For r from 1 and c from 1, compare matrix[r][c] with matrix[r-1][c-1].
  2. Return false on the first mismatch, true otherwise.

Why it works

Two consecutive cells on a diagonal differ by (1, 1), so checking each such pair covers every adjacent pair on every diagonal, and constancy along a diagonal follows by induction.

Complexity

  • Time — O(m · n)
  • Space — O(1)

Pitfalls

  • Starting either loop at 0 reads out of bounds.
  • For a matrix streamed one row at a time, compare each row with the previous row shifted by one.

Reference solution

Python

def isToeplitzMatrix(matrix) -> bool:
    for r in range(1, len(matrix)):
        for c in range(1, len(matrix[0])):
            if matrix[r][c] != matrix[r - 1][c - 1]:
                return False
    return True

Java

public static boolean isToeplitzMatrix(int[][] matrix) {
    for (int r = 1; r < matrix.length; r++) {
        for (int c = 1; c < matrix[0].length; c++) {
            if (matrix[r][c] != matrix[r - 1][c - 1]) return false;
        }
    }
    return true;
}

C++

bool isToeplitzMatrix(vector<vector<int>>& matrix) {
    for (size_t r = 1; r < matrix.size(); r++) {
        for (size_t c = 1; c < matrix[0].size(); c++) {
            if (matrix[r][c] != matrix[r - 1][c - 1]) return false;
        }
    }
    return true;
}

JavaScript

var isToeplitzMatrix = function(matrix) {
    for (let r = 1; r < matrix.length; r++) {
        for (let c = 1; c < matrix[0].length; c++) {
            if (matrix[r][c] !== matrix[r - 1][c - 1]) return false;
        }
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal