0596EasyArrayMatrix

Banded Woven Panel

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A loom produces a rectangular panel of coloured squares, handed to you as matrix, where matrix[i][j] is the colour code woven into row i, column j.

A band of the panel is traced by starting on some square and stepping repeatedly one row down and one column to the right, until the next step would leave the panel. Every square of the panel lies on exactly one band.

The panel is cleanly banded when all the squares of each band carry the same colour code. Return true when the panel is cleanly banded and false otherwise.

Examples

Example 1

Input: matrix = [[3, 7, 1], [4, 3, 7], [9, 4, 3]]
Output: true

The bands hold the colour codes 3, 3, 3 then 7, 7 then 1 then 4, 4 then 9, and every band carries a single code.

Example 2

Input: matrix = [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
Output: false

The band starting at row 0, column 0 visits the codes 1, 2 and 3, which are not all equal, so the panel is not cleanly banded.

Example 3

Input: matrix = [[99, 98], [0, 99]]
Output: true

One band holds 99 and 99, and the remaining two bands hold a single square each, so every band is uniform.

Constraints

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

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def is_toeplitz_matrix(matrix: list[list[int]]) -> bool:

Java

public boolean isToeplitzMatrix(int[][] matrix)

The intended approach

Time O(m * n): one comparison per square away from the top row and left column.Space O(1) beyond the input panel.

A square and the square one row up and one column to its left always belong to the same band, and every square other than those in the first row or first column has such a partner. So the panel is cleanly banded exactly when each square from row 1 and column 1 onward equals its up-left partner. One sweep over the panel checking that equality settles it, with nothing stored.

Pythonentry point: is_toeplitz_matrix

def is_toeplitz_matrix(matrix):
    # O(m * n) time, O(1) extra space. Two squares lie on the same diagonal
    # exactly when one can be reached from the other by repeated steps of one row
    # down and one column right, so a diagonal is uniform precisely when every
    # square on it matches the square immediately up and to its left.
    rows = len(matrix)
    cols = len(matrix[0])
    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][c] != matrix[r - 1][c - 1]:
                return False
    return True

The obvious version

Collect the colour codes of every square into buckets keyed by the row index minus the column index, which is the same for all squares of one band, then check each bucket against its own first entry.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_is_toeplitz_matrix(matrix):
    buckets = {}
    for r in range(len(matrix)):
        for c in range(len(matrix[0])):
            key = r - c
            if key not in buckets:
                buckets[key] = []
            buckets[key].append(matrix[r][c])
    for key in buckets:
        colours = buckets[key]
        for colour in colours:
            if colour != colours[0]:
                return False
    return True

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in