Log inSign up
easyLeetCodeNot Started

Toeplitz Matrix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an m x n matrix, return true *if the matrix is Toeplitz. Otherwise, return* false.

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

Example 1 · Valid 3x4 Toeplitz Matrix:

Input: matrix = [[1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]]
Output: true
Explanation: The diagonals are: - "[9]" - "[5, 5]" - "[1, 1, 1]" - "[2, 2, 2]" - "[3, 3]" - "[4]" In each diagonal all elements are the same, so the answer is true.

Example 2 · Invalid Diagonal Matrix:

Input: matrix = [[1, 2], [2, 2]]
Output: false
Explanation: The diagonal "[1, 2]" has different elements, so the answer is false.

Example 3 · Single Row or Single Column Matrix:

Input: matrix = [[1, 2, 3, 4]]
Output: true
Explanation: All diagonals have length 1, so the matrix is trivially Toeplitz.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D matrix indexing matrix[r][c]
  • Diagonal relationships in grids (row - col is constant along top-left to bottom-right diagonals)
  • Boundary coordinate conditions

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the local equivalence property of Toeplitz diagonals.
  • Eliminate diagonal hash maps by comparing adjacent neighbors directly.
  • Formulate follow-ups for out-of-memory and streaming matrix rows.
  • Write concise, standalone solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Checking diagonal consistency in a 2D grid from top-left to bottom-right.
  • Any cell (r, c) belongs to the same diagonal as (r - 1, c - 1).
  • Requires O(1) space with simple neighbor verification.

Algorithmic Decision Tree:

  • Whenever checking top-left to bottom-right diagonals: Compare each cell (r, c) with its predecessor (r - 1, c - 1) for all r >= 1, c >= 1.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Diagonal by Diagonal Traversal from Borders

Intuition

Iterate through every diagonal individually by starting at each border cell in the first row and first column.

Algorithm

  1. 1. For col from 0 to n-1: trace diagonal from (0, col). If any cell != matrix[0][col], return false.
  2. 2. For row from 1 to m-1: trace diagonal from (row, 0). If any cell != matrix[row][0], return false.
  3. 3. Return true.

Diagonal-by-Diagonal Border Traversal

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 1, 1, 2, 2, 3]
Current operationSTEP 1 OF 6
Phase 1 — Trace Main Diagonal from (0,0): Start at apex (0,0) val=1
Visual state
Values and pointers at this exact step
array
S
1
1
1
2
2
3
0
↑ Diag 0
1
2
3
4
5
Variables at this step
Diagonal Start
(0,0)
Diagonal Values
[1, 1, 1]
Valid
true
Check / comparison
matrix[0][0] == matrix[1][1] == matrix[2][2] == 1.
Decision / next transition
Main diagonal validated.
Why this step matters

Phase 1 — Trace Main Diagonal from (0,0): Start at apex (0,0) val=1. Follow diagonal down-right: (1,1) val=1, (2,2) val=1. All equal.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 bool isToeplitzMatrix(vector<vector<int>>& matrix) {
17 int m = matrix.size(), n = matrix[0].size();
18 for (int c = 0; c < n; ++c) {
19 int val = matrix[0][c], r = 0, col = c;
20 while (r < m && col < n) {
21 if (matrix[r++][col++] != val) return false;
22 }
23 }
24 for (int r = 1; r < m; ++r) {
25 int val = matrix[r][0], row = r, col = 0;
26 while (row < m && col < n) {
27 if (matrix[row++][col++] != val) return false;
28 }
29 }
30 return true;
31 }
32};
33
34int main() {
35 Solution sol;
36 vector<vector<int>> matrix = {{1, 2, 3, 4}, {5, 1, 2, 3}, {9, 5, 1, 2}};
37 bool ans = sol.isToeplitzMatrix(matrix);
38 cout << "Is Toeplitz Matrix: " << (ans ? "true" : "false") << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(M * N) — Visits each matrix cell exactly once along diagonals in O(M * N) time.
  • Space complexity: O(1) — Auxiliary space is O(1).

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Hash Map Grouping by Diagonal Index (r - c)

Intuition

Every cell on a diagonal shares the same constant index (r - c). Store first seen value for each key.

Algorithm

  1. 1. Initialize Hash Map diagMap.
  2. 2. For r from 0 to m-1 and c from 0 to n-1: - key = r - c - If key in diagMap and diagMap[key] != matrix[r][c], return false. - diagMap[key] = matrix[r][c].
  3. 3. Return true.

Hash Map Grouping by Diagonal Index (r - c)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 9]
Current operationSTEP 1 OF 6
Phase 1 — Invariant Principle: Cells belonging to the same top-left to bottom-right diagonal share the identical coordinate difference: (r - c)
Visual state
Values and pointers at this exact step
array
S
1
2
3
4
5
9
0
↑ Start
1
2
3
4
5
Variables at this step
Map
{}
Formula
key = r - c
Check / comparison
Map key = (r - c).
Decision / next transition
Initialize groups = {}.
Why this step matters

Phase 1 — Invariant Principle: Cells belonging to the same top-left to bottom-right diagonal share the identical coordinate difference: (r - c). Store first-seen value in map.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 bool isToeplitzMatrix(vector<vector<int>>& matrix) {
17 unordered_map<int, int> diagMap;
18 int m = matrix.size(), n = matrix[0].size();
19 for (int r = 0; r < m; ++r) {
20 for (int c = 0; c < n; ++c) {
21 int key = r - c;
22 if (diagMap.count(key) && diagMap[key] != matrix[r][c]) {
23 return false;
24 }
25 diagMap[key] = matrix[r][c];
26 }
27 }
28 return true;
29 }
30};
31
32int main() {
33 Solution sol;
34 vector<vector<int>> matrix = {{1, 2, 3, 4}, {5, 1, 2, 3}, {9, 5, 1, 2}};
35 bool ans = sol.isToeplitzMatrix(matrix);
36 cout << "Is Toeplitz Matrix: " << (ans ? "true" : "false") << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(M * N) — Single traversal of all M x N elements with O(1) map operations in O(M * N) time.
  • Space complexity: O(M + N) — Stores M + N - 1 unique diagonal keys, consuming O(M + N) space.

3. Direct Adjacent Cell Invariant Check (Optimal & Standard)

Intuition

Check if each cell (r, c) equals its top-left neighbor (r-1, c-1) for all r > 0 and c > 0.

Algorithm

  1. 1. For r from 1 to m-1: - For c from 1 to n-1: - If matrix[r][c] != matrix[r-1][c-1], return false.
  2. 2. Return true in O(M * N) time and O(1) space.

Direct Adjacent Invariant Check (matrix[r][c] == matrix[r-1][c-1])

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 5, 1, 2]
Current operationSTEP 1 OF 6
Phase 1 — Local Invariant Formulation: A matrix is Toeplitz if and only if EVERY cell (r, c) with r > 0 and c > 0 equals its top-left neighbor matrix[r - 1][c - 1]
Visual state
Values and pointers at this exact step
array
S
1
2
3
5
1
2
0
↑ r=1, c=1
1
2
3
4
5
Variables at this step
r
1
c
1
Formula
matrix[r][c] == matrix[r-1][c-1]
Check / comparison
Invariant: matrix[r][c] == matrix[r-1][c-1]. Zero extra space needed.
Decision / next transition
Begin loop r from 1 to 2, c from 1 to 3.
Why this step matters

Phase 1 — Local Invariant Formulation: A matrix is Toeplitz if and only if EVERY cell (r, c) with r > 0 and c > 0 equals its top-left neighbor matrix[r - 1][c - 1].

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 bool isToeplitzMatrix(vector<vector<int>>& matrix) {
17 for (size_t r = 1; r < matrix.size(); ++r) {
18 for (size_t c = 1; c < matrix[0].size(); ++c) {
19 if (matrix[r][c] != matrix[r - 1][c - 1]) {
20 return false;
21 }
22 }
23 }
24 return true;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<vector<int>> matrix = {{1, 2, 3, 4}, {5, 1, 2, 3}, {9, 5, 1, 2}};
31 bool ans = sol.isToeplitzMatrix(matrix);
32 cout << "Is Toeplitz Matrix: " << (ans ? "true" : "false") << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(M * N) — Single pass checks (M-1) * (N-1) comparisons in optimal O(M * N) time.
  • Space complexity: O(1) — Requires 0 auxiliary heap allocations. Auxiliary space is strictly O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Diagonal by Diagonal Traversal from BordersO(M * N)O(1)Iterate through every diagonal individually by starting at each border cell in the first row and first column.Repeated redundant scans over the input.
2.Approach 2: Hash Map Grouping by Diagonal Index (r - c)O(M * N)O(M + N)Every cell on a diagonal shares the same constant index (r - c). Store first seen value for each key.Auxiliary memory allocation or sorting step.
3.Approach 3: Direct Adjacent Cell Invariant Check (Optimal & Standard)OptimalO(M * N)O(1)Check if each cell (r, c) equals its top-left neighbor (r-1, c-1) for all r > 0 and c > 0.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • 1x1 Matrix (Single Cell) — Input: matrix = [[1]], Expected: true — Loops starting at r=1 and c=1 do not execute; returns true immediately.
  • Single Row Matrix (1xN) — Input: matrix = [[1, 2, 3]], Expected: true — All diagonals have length 1; returns true.
  • Mismatch on the Bottom-Right Corner — Input: matrix = [[1, 2], [3, 4]], Expected: false — matrix[1][1] (4) != matrix[0][0] (1) -> returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Toeplitz Matrix?

2.Why is the brute force approach suboptimal for large inputs in Toeplitz Matrix?

3.Which data structure or technique enables the optimal solution for Toeplitz Matrix?

Back to DSA Sheet