Same Value Along Every Diagonal
Problem
A test pattern for a display is stored as a grid of numbers. It is valid only when every diagonal running from top-left to bottom-right holds a single repeated value. Given the grid, return True if it is valid and False otherwise. The grid has between 1 and 20 rows and between 1 and 20 columns, and each value is between 0 and 99.
Examples
Input: grid = [[1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]]
Output: True
Why: the diagonals are [9], [5, 5], [1, 1, 1], [2, 2, 2], [3, 3] and [4]Input: grid = [[1, 2], [2, 2]]
Output: False
Why: the main diagonal holds 1 and then 2Input: grid = [[7]]
Output: True
Why: edge case, a single cell is one diagonal with one valueHints
0 / 3
Two cells sit on the same top-left to bottom-right diagonal exactly when their row minus column is the same.
You do not need to collect whole diagonals. It is enough that every cell matches the cell just up and to the left of it, because equality then chains along the diagonal.
Loop over every cell that has an up-left neighbour, which is every cell outside the first row and first column, and return False at the first mismatch.
Solution
Moving one step down and one step right keeps row minus column unchanged, so each cell's diagonal predecessor is the cell at row - 1, column - 1. If every cell equals that predecessor, equality chains from the first cell of each diagonal to its last, so the whole diagonal holds one value; a single mismatch breaks it. Checking each cell against its neighbour needs no extra storage, and the same check works if rows arrive one at a time, since each new row only has to match the previous row shifted right by one. Time is O(rows × cols) and space is O(1).
def diagonal_constant(grid):
for r in range(1, len(grid)):
for c in range(1, len(grid[0])):
if grid[r][c] != grid[r - 1][c - 1]: # up-left neighbour differs
return False
return True
print(diagonal_constant([[1, 2, 3, 4], [5, 1, 2, 3], [9, 5, 1, 2]])) # -> True
print(diagonal_constant([[1, 2], [2, 2]])) # -> False
print(diagonal_constant([[7]])) # -> TrueStuck on the idea rather than the code? Rotate In Place covers it.