1511. Is Every Diagonal Constant

An R by C grid is given. Print YES if every diagonal running down and to the right holds a single repeated value, and NO otherwise. Two cells are on the same such diagonal when column - row is equal.

1 2 3 4 -> YES the diagonals are 9, 5 5, 1 1 1, 2 2 2, 3 3, 4 5 1 2 3 9 5 1 2

1 2 3 4 -> NO the 9 in the last row breaks the 3 3 diagonal 5 1 2 3 9 5 9 2

1 2 3 4 5 6 -> YES a single row: no diagonal holds two cells at all

## What most people try first

Grouping the cells by column - row, storing each group, and checking that each is constant. That is correct and it stores the whole grid a second time. It also needs the shifted key from problem 1508, since column - row is negative for cells below the main diagonal.

The other reflex is to compare every cell only against the FIRST cell of its diagonal, which requires knowing where that first cell is: on the top row for a non-negative key, on the left edge otherwise. That is two cases for a check that needs none.

## Compare each cell with its up-left neighbour

for i in 1 .. R-1: for j in 1 .. C-1: if g[i][j] != g[i-1][j-1]: print NO and stop print YES

## Why the neighbour comparison is enough

Two cells are on the same diagonal exactly when one is reached from the other by repeatedly stepping down and right. Equality is transitive, so a diagonal is constant exactly when every adjacent pair along it agrees, and every adjacent pair along every diagonal is exactly one (i, j) with i >= 1 and j >= 1 compared against (i-1, j-1). Nothing is missed and nothing is checked twice.

Cells in row 0 or column 0 start a diagonal and have no up-left neighbour, so the loops start at 1 in both indices. That is the whole reason for the bounds.

## The degenerate answers

A 1 by C grid or an R by 1 grid has no diagonal longer than one cell, so the answer is always YES and the loop body never runs. A correct implementation gets that for free. One that assumes a diagonal has at least two cells, for instance by indexing g[1][1] before checking the shape, crashes.

## Only one row needs to be in memory

The comparison only looks one row back, so the grid can be checked as it is read with a single row of C values held. That is O(C) extra rather than O(R C), and it is the reason this check is the standard one.

## Cost

O(R C) time and O(C) extra memory, or O(1) beyond the grid if the grid is already stored. Values fit in a signed 32 bit integer, whose limit is 2147483647, and nothing is combined.

Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `-10^9 ≤ each value ≤ 10^9` - `R` and `C` are independent; the grid need not be square