Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Build confidence with an intuition-first walkthrough focused on array fundamentals.
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:
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]] Output: true Explanation: In the above grid, 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:
Input: matrix = [[1,2],[2,2]] Output: false Explanation: The diagonal "[1, 2]" has different elements.
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200 <= matrix[i][j] <= 99Follow up:
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?matrix is so large that you can only load up a partial row into the memory at once?Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[[1,2,3,4],[5,1,2,3],[9,5,1,2]]
[[1,2],[2,2]]
valid-word-square)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #766: Toeplitz Matrix
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;
}
}
// Accepted solution for LeetCode #766: Toeplitz Matrix
func isToeplitzMatrix(matrix [][]int) bool {
m, n := len(matrix), len(matrix[0])
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][j] != matrix[i-1][j-1] {
return false
}
}
}
return true
}
# Accepted solution for LeetCode #766: Toeplitz Matrix
class Solution:
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
m, n = len(matrix), len(matrix[0])
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] != matrix[i - 1][j - 1]:
return False
return True
// Accepted solution for LeetCode #766: Toeplitz Matrix
impl Solution {
pub fn is_toeplitz_matrix(matrix: Vec<Vec<i32>>) -> bool {
let (m, n) = (matrix.len(), matrix[0].len());
for i in 1..m {
for j in 1..n {
if matrix[i][j] != matrix[i - 1][j - 1] {
return false;
}
}
}
true
}
}
// Accepted solution for LeetCode #766: Toeplitz Matrix
function isToeplitzMatrix(matrix: number[][]): boolean {
const [m, n] = [matrix.length, matrix[0].length];
for (let i = 1; i < m; ++i) {
for (let j = 1; j < n; ++j) {
if (matrix[i][j] !== matrix[i - 1][j - 1]) {
return false;
}
}
}
return true;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.